变异蛮牛时间限制1秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述幽怨火憎恨焰变异蛮牛续执念。给定一棵根为1 11且是黑点的有根树。每个白点相邻所有的点都是黑点每个黑点相邻所有的点都是白点。换句话说你可以从根结点开始按照深度对每个点黑白染色。现在对于一条两个端点分别是u , v u,vu,v的链定义其长度为包含的黑点个数 −− 包含的白点个数。请你数一数长度最大的链的个数。输入描述全文第一行是T ( 1 ≤ T ≤ 10 5 ) T(1≤T≤10^5)T(1≤T≤105)表示数据组数接下来T TT组数据先输入一行一个正整数表示树的大小n ( 1 ≤ n ≤ 2 × 10 5 , ∑ n ≤ 3 × 10 6 ) n(1≤n≤2×10^5,∑n≤3×10^6)n(1≤n≤2×105,∑n≤3×106)接下来输入n − 1 n−1n−1行每行两个正整数u , v ( 1 ≤ u , v ≤ n ) u,v(1≤u,v≤n)u,v(1≤u,v≤n)表示树的一条边。输出描述输出T TT行每行一个整数表示答案。示例1输入1 6 1 2 2 3 3 4 4 5 5 6输出6说明合法的链分别是{ 1 } , { 3 } , { 5 } , { 1 , 2 , 3 } , { 3 , 4 , 5 } , { 1 , 2 , 3 , 4 , 5 } \{1\},\{3\},\{5\},\{1,2,3\},\{3,4,5\},\{1,2,3,4,5\}{1},{3},{5},{1,2,3},{3,4,5},{1,2,3,4,5}。解题思路本题的关键在于理解树的黑白染色性质与链长度的定义将问题转化为统计某种颜色节点的数量并计算组合数。1. 问题转化染色规则树根为黑色相邻节点颜色不同即按照深度交替染色深度为偶数的黑奇数为白或反之。链的长度定义一条链上黑点个数减去白点个数。因为颜色是交替的对于任意一条链两端点同色时长度为1 11两端点异色时长度为0 00长度为− 1 -1−1的情况对应两端均为白色。因此最大长度只能是1 11。最大长度链的形态所有长度为1 11的链即包括单个黑点视为长度为1 11的链以及两个黑点作为端点的路径。计数设树中共有c cc个黑点则长度为1 11的链总数即为c cc个单点链加上任意两个黑点之间的路径数答案 c ( c 2 ) c ( c 1 ) 2 \text{答案} c \binom{c}{2} \frac{c(c1)}{2}答案c(2c​)2c(c1)​任意两个黑点之间的路径必然长度为1 11且是唯一简单路径。2. 算法实现DFS 染色与计数从根节点1 11开始 DFS用dep数组记录颜色dep[root]0表示黑色子节点颜色为dep[parent] ^ 1。遍历过程中统计dep为0 00的节点数量c cc。输出对每组数据输出c × ( c 1 ) / 2 c \times (c1) / 2c×(c1)/2。多组数据注意清空邻接表与重置相关变量。3. 复杂度分析时间复杂度每组数据O ( n ) O(n)O(n)所有数据的总节点数∑ n ≤ 3 × 10 6 \sum n \le 3\times 10^6∑n≤3×106总时间线性可行。空间复杂度邻接表O ( n ) O(n)O(n)dep数组O ( n ) O(n)O(n)。总结利用黑白交替染色推导出最大链长度必然为1 11并将所有长度为1 11的链等价于黑点及其两两配对路径直接统计黑点个数即可组合计算出答案。代码简要说明dfs(u, p)计算dep如果dep[u]0则计数器c cc加一递归遍历子树。主函数读入T TT对每组数据建图DFS 从0 00号节点原题1 11号开始输出c ( c 1 ) / 2 c(c1)/2c(c1)/2并清空图。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll c0;vectorllg[200000];ll dep[200000];voiddfs(ll u,ll p){if(dep[u]0)c;ll i0;for(i0;i(ll)g[u].size();i){if(g[u][i]p)continue;dep[g[u][i]]dep[u]^1;dfs(g[u][i],u);}}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll T,n,u,v,i;cinT;while(T--){cinn;for(i0;in-1;i){cinuv;g[u-1].push_back(v-1);g[v-1].push_back(u-1);}c0;dfs(0,-1);coutc*(c1)/2\n;for(i0;in;i)g[i].clear();dep[0]0;}return0;}