小红树【牛客tracker 每日一题】

小红树时间限制1 秒空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述小红拿到了一棵树每个节点被染成了红色或者蓝色。小红定义每条边的权值为删除这条边时形成的两个子树的同色连通块数量之差的绝对值。小红想知道所有边的权值之和是多少输入描述第一行输入一个正整数n nn代表节点的数量。第二行输入一个长度为n nn且仅由R和B两种字符构成的字符串第i ii个字符为R代表i ii号节点被染成红色为B则被染成蓝色。接下来的n − 1 n - 1n−1行每行输入两个正整数u uu和v vv代表节点u uu和节点v vv有一条边相连。1 ≤ n ≤ 200000 1 \le n \le 2000001≤n≤200000输出描述一个正整数代表所有节点的权值之和。注题面原文写的是“所有节点的权值之和”但结合描述与示例实际所求为所有边的权值之和。示例 1输入4 BBRR 1 2 3 2 4 1输出2说明该树的示意图如下1(B) / \ 2(B) 4(R) / 3(R)1 - 2 1\text{-}21-2这条边的权值为0 00因为删除后两个子树的同色连通块都是2 22。3 - 2 3\text{-}23-2这条边的权值为1 11因为删除后两个子树的同色连通块数量分别是1 11和2 22。1 - 4 1\text{-}41-4这条边的权值为1 11因为删除后两个子树的同色连通块数量分别是2 22和1 11。答案为0 1 1 2 0 1 1 20112。数据范围与提示1 ≤ n ≤ 200000 1 \le n \le 2000001≤n≤200000字符集为{ R , B } \{\texttt{R}, \texttt{B}\}{R,B}核心思路先做一次树形 DP求出以1 11为根时每棵子树v vv内部的同色连通块数量c n t v cnt_vcntv​c n t v 1 ∑ c ∈ s o n ( v ) ( c n t c − [ c o l o r ( v ) c o l o r ( c ) ] ) cnt_v 1 \sum_{c \in son(v)} \left( cnt_c - [\,color(v) color(c)\,] \right)cntv​1c∈son(v)∑​(cntc​−[color(v)color(c)])其中若v vv与子节点c cc同色则v vv所在块与c cc所在块会合并成一个故减1 11。整棵树的总连通块数C c n t 1 C cnt_{1}Ccnt1​。对一条边( u , v ) (u, v)(u,v)v vv为子节点删除后两侧块数分别为c n t v 和 C − c n t v [ c o l o r ( u ) c o l o r ( v ) ] cnt_v \quad\text{和}\quad C - cnt_v [\,color(u) color(v)\,]cntv​和C−cntv​[color(u)color(v)]后者含义是若父子同色切断后父侧需要单独“补回”一块。该边权值即为两者之差的绝对值累加所有边即得答案。由于n nn可达2 × 10 5 2 \times 10^52×105递归 DFS 可能爆栈建议改用显式栈的迭代写法或手动调大栈空间。时间复杂度O ( n ) O(n)O(n)。解题思路本题是树形 DP 同色连通块计数的经典问题。给定一棵树每个节点染成红色或蓝色。定义每条边的权值为删除该边后形成的两个子树中同色连通块数量之差的绝对值。求所有边的权值之和。1. 问题等价转化同色连通块在树中若两个相邻节点颜色相同则它们属于同一个同色连通块否则属于不同块。对于任意节点u uu设f [ u ] f[u]f[u]表示以u uu为根的子树内部包含u uu的同色连通块数量。整棵树的总同色连通块数量记为C f [ 1 ] C f[1]Cf[1]以 1 为根。考虑一条边( u , v ) (u, v)(u,v)其中v vv是u uu的子节点。删除这条边后树被分成两部分以v vv为根的子树其内部同色连通块数为f [ v ] f[v]f[v]。剩余部分包含u uu及其他节点其同色连通块数需要重新计算。原本整棵树的总块数为C CC去掉v vv子树后若u uu与v vv同色则原本它们所在的块是合并的删除边后这个块分裂因此剩余部分的块数比C − f [ v ] C - f[v]C−f[v]多 1若u uu与v vv异色则删除边不会造成额外分裂剩余部分块数就是C − f [ v ] C - f[v]C−f[v]。因此剩余部分的同色连通块数为other C − f [ v ] [ color ( u ) color ( v ) ] \text{other} C - f[v] [\text{color}(u) \text{color}(v)]otherC−f[v][color(u)color(v)]该边的权值即为∣ f [ v ] − other ∣ |f[v] - \text{other}|∣f[v]−other∣累加所有边的权值即得答案。2. 算法实现建树读入n nn和颜色字符串s ss下标从 1 开始用邻接表存储无向边。第一次 DFSd1计算子树同色连通块数从根节点 1 出发递归遍历所有子节点。初始化f [ u ] 1 f[u] 1f[u]1。对于每个子节点x xx先递归求出f [ x ] f[x]f[x]然后累加f [ u ] f [ x ] f[u] \mathrel{} f[x]f[u]f[x]。若s [ u ] s [ x ] s[u] s[x]s[u]s[x]说明u uu与x xx同色它们所在的块合并因此f [ u ] − 1 f[u] \mathrel{-} 1f[u]−1。最终f [ 1 ] f[1]f[1]即为整棵树的总同色连通块数C CC。第二次 DFSd2累加边权再次从根节点 1 出发遍历每条边( u , x ) (u, x)(u,x)x xx为子节点。计算剩余部分的块数v f[1] - f[x]若s [ u ] s [ x ] s[u] s[x]s[u]s[x]则v。边权为abs(v - f[x])累加到答案ans。递归处理子节点。输出答案ans即为所有边权之和。3. 复杂度分析时间复杂度两次 DFS 均遍历所有节点和边一次每次操作O ( 1 ) O(1)O(1)总时间复杂度O ( n ) O(n)O(n)。n ≤ 2 × 10 5 n \le 2\times 10^5n≤2×105完全可行。空间复杂度邻接表O ( n ) O(n)O(n)数组f ff和递归栈深度O ( n ) O(n)O(n)建议使用迭代或手动扩栈防止爆栈。总结通过树形 DP 预处理出每棵子树的同色连通块数量再利用整棵树的总块数推导出删除任意边后两侧的块数。核心在于理解“同色边合并”导致删除时可能产生额外分裂。算法线性高效能够处理2 × 10 5 2\times 10^52×105规模的数据。代码简要说明全局变量n节点数s颜色字符串g邻接表f[N]存储子树同色连通块数ans累加边权。d1(u, fa)函数后序遍历计算f [ u ] f[u]f[u]。先置f [ u ] 1 f[u]1f[u]1对每个子节点x xx递归累加f [ x ] f[x]f[x]若同色则减 1。d2(u, fa)函数前序遍历处理边权。对每个子节点x xx先递归处理x xx然后计算剩余部分块数v f[1] - f[x] (s[u]s[x])累加abs(v - f[x])到ans。主函数读入数据建图调用d1(1, -1)和d2(1, -1)输出ans。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N2e510;constll INF1e18;constll M1e610;constll mod1e97;ll n;ll f[N];string s;vectorllg[N];ll ans;voidd1(ll u,ll fa){f[u]1;for(ll x:g[u]){if(xfa)continue;d1(x,u);f[u]f[x];if(s[u]s[x])f[u]--;}}voidd2(ll u,ll fa){for(ll x:g[u]){if(xfa)continue;d2(x,u);ll vf[1]-f[x];if(s[u]s[x])v;ansabs(v-f[x]);}}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll a,b;cinns;s$s;n--;while(n--){cinab;g[a].push_back(b);g[b].push_back(a);}d1(1,-1);d2(1,-1);coutansendl;return0;}