运行要求运行时限：2sec内存限制：1024MB题目多叉树G有N个顶点。顶点从1到N编号，并累积一次。多叉树的第i个分支由顶点ai和bi连接。现在考虑给多叉树G的树枝上色，这时候对颜色有需求。即从任意一个顶点开始，要求与该顶点相连的边的颜色不同。在满足上述条件的配色方案中，哪种方案使用的颜色最少？要求2<=N<=1000001<=ai<=bi<=N所有输入都是整数给定的图是一个树结构输入输入是根据以下标准从命令行输入的Na1b1a2b2...aN-1bN-1output输出行数为N行。第一行输出中使用的颜色数。第i+1行（1<=i<=N-1）输出用于表示第i个分支颜色的ci。这里ci必须满足1<=ci<=K。满足条件的配色方案可能有很多种，使用最少颜色的配色方案也可能有很多种。可以选择其中一个输出例1输入31223输出212例2输入812232425475668输出41234112例3输入61213141516输出512345解题思路读懂题目1.多叉树上有N个顶点。i为支路编号，满足i<=N-1。总结一下条件就是有N个顶点，N-1个分支2。我们以例子2为例812232425475668N=8，有8个点。我们依次编号为1、2、3、4、5、6、7、8。第一个分支是第一个点和第二个点之间的连接线。第二支是第二点和第三点的连线。第三条支线是第二点和第四点的连线。...第7个分支是连接第6个点和第8个点的线。图13.满足条件的着色方案如下图所示，所有顶点连接的分支的颜色是不同的。图24不满足条件的配色方案如下图所示。连接顶点2的两条分支都是红色的，不符合要求。图35.如何满足最小颜色。让我们尝试优化图2中顶点2的连接分支。第1条边、第2条边、第3条边和第4条边连接到同一个顶点，因此颜色必须保持不同。对于第5面，我们其实可以用第1面的红色，第6面，我们也可以用第1面的红色。如果第6面是红色，第7面的颜色是为了和第6面保持不同，可以使用现有的紫色，但是为了保持色量成本，第二面的橙色也可以使用。然后我们可以得到如图4所示的优化结果。在图4中，我们将对每种颜色进行编号。红色为1，橙色为2，黄色为3，绿色为4。按照第一条边到第七条边的顺序，我们可以得到1,2,3,4,1,1,2的结果。解决思路至少有多少种颜色？连接到每个顶点的分支的颜色需要不同。借色如下图，顶点4和5都是只有两个分支的顶点，可以从有4个分支的顶点2借用红色。颜色其实可以抽象成数字，这些数字的排列可以看做是从1开始的累加，但是如果相邻的顶点还有其他标记为M的分支，累加时必须跳过M。请在此处查看动画中的跳过。具体步骤是找到任意一个顶点X，开始DFS遍历。遍历到顶点N的分支时，对顶点N的每条分支做累加标记。如果顶点N来自M，且M到N的分支的标签为X，则累加该分支时必须跳过M标记顶点N。最后以分支最多的顶点的分支数为序，输出分支的标记动画代码fromsysimportsetrecursionlimitsetrecursionlimit(100000)n=int(input())arr=[]foriinrange(n-1):S=input()ar=[int(s)forsinS.split("")]arr.append(ar)defprepare(n,arr):数据=[[]foriinrange(n)]nodeStates=[-1foriinrange(n)]childNums=[0foriinrange(n)]forarinarr:start=ar[0]-1to=ar[1]-1data[start].append(to)data[to].append(start)返回数据，nodeStates,childNumsdata,nodeStates,childNums=prepare(n,arr)mmk={}defgenerateID(开始，到）：如果开始<到：开始，到=到，开始返回开始*100000+todefdfs（currentNode，arr，x）：childNodes=arr[currentNode]nodeStates[currentNode]=1childNums[currentNode]=len(childNodes)kk=0forchinchildNodes:ifnodeStates[ch]==-1:kk=kk+1ifkk==x:kk=kk+1mmk[generateID(currentNode+1,ch+1)]=kkdfs(ch,arr,kk)dfs(0,data,-1)print(max(childNums))forarinarr:start=ar[0]to=ar[1]print(mmk[generateID(start,to)])注意fromsysimportsetrecursionlimitsetrecursionlimit(100000)这个要加上，否则会根据分支两端的顶点输出runtimeerror错误编号，利用python的字典完成分支信息的高速读取和输出
