题解：CF2195E

题面Idiot First Search有一棵包含n 1 n 1n1个顶点的二叉树n nn为奇数定点编号为0 , 1 , ⋯ , n 0 , 1 , \cdots , n0,1,⋯,n。每个顶点最多可写入一个字母初始时所有顶点均为空。树的根节点是顶点0 00。在这棵树中顶点0 00是顶点1 11的父节点其余所有节点要么有2 22个子节点要么没有子节点。鲍勃迷失在树中的某个顶点上他希望通过到达顶点0 00逃离这棵树。他自创了一种遍历树的新方式“笨蛋优先搜索”。当鲍勃位于顶点v vv1 ≤ v ≤ n 1 \le v \le n1≤v≤n时他的移动规则如下若顶点v vv是叶子节点鲍勃总是移动到v vv的父节点否则按以下条件以此判断若顶点v vv上没有字母鲍勃在v vv上写入字母L然后移动到v vv的左子节点若顶点v vv上写着L鲍勃将其改为R然后移动到v vv的右子节点若顶点v vv上写着R鲍勃将其擦除然后移动到v vv的父节点。鲍勃移动到相邻顶点恰好需要1 11秒因此完成x xx次移动总共需要x xx秒。由题意可知鲍勃一定能在有限的时间内移动到顶点0 00。对于每个顶点k 1 , 2 , ⋯ , n k {1 , 2 , \cdots , n}k1,2,⋯,n计算鲍勃从顶点k kk出发到顶点0 00所用的总时间以秒为单位。由于数值可能极大输出计算结果对10 9 7 10 ^ 9 71097取模后的值。输入每个测试点包含多个测试用例。测试点的第一行为测试用例的数量t tt1 ≤ t ≤ 10 4 1 \le t \le 10^41≤t≤104。每个测试用例的输入格式如下所示。对于每个测试用例第一行是一个奇数n nn1 ≤ n ≤ 3 × 10 5 1 1 \le n \le 3 \times 10 ^ 5 11≤n≤3×1051。接下来n nn行每行两个整数l i l _ ili​和r i r _ iri​表示顶点i ii的子节点0 ≤ l i ≤ n , 0 ≤ r i ≤ n 0 \le l _ i \le n , 0 \le r _ i \le n0≤li​≤n,0≤ri​≤n。如果顶点i ii没有子节点则l i r i 0 l _ i r _ i 0li​ri​0。保证输入的是一个合法的、符合题目条件的二叉树。保证一个测试点中所有测试用例的n nn的总和不超过3 × 10 5 1 3 \times 10 ^ 5 13×1051。输出对于每个测试用例在一行内输出n nn个整数τ 1 , τ 2 , ⋯ , τ n \tau _ 1 , \tau _ 2 , \cdots , \tau _ nτ1​,τ2​,⋯,τn​用空格隔开。其中τ k \tau _ kτk​表示从顶点k kk到顶点0 00所需要的时间对10 9 7 10 ^ 9 71097后的结果。思路tag \text{tag}tagdfs“笨蛋优先搜索”的核心走法是先将以k kk为根的子树深度优先遍历一遍再走到其父节点并将以它为根的子树深度优先遍历一遍以此类推移至到顶点0 00。由图论常识可知令s i z e k size _ ksizek​为以顶点k kk为根的子树大小包括顶点k kk自己则深度优先遍历该子树的时间即为2 s i z e k − 2 2 size _ k - 22sizek​−2。再加上走到k kk的父节点的时间即遍历该子树并回到根节点的父节点的时间为2 s i z e k − 1 2 size _ k - 12sizek​−1。记此式为t k t _ ktk​则τ k τ f a k t k \tau _ k \tau _ {fa _ k} t _ kτk​τfak​​tk​省略取模。s i z e k size _ ksizek​容易 dfs 求出第二遍 dfs 求出τ k \tau_ kτk​记得取模最后输出答案故总时间复杂度为O ( ∑ n ) O(\sum n)O(∑n)。代码#includebits/stdc.h#defineintlonglongusingnamespacestd;constintmaxn3e55,mod1e97;intl[maxn],r[maxn],fa[maxn];intsz[maxn],ans[maxn];intn;voiddfs(intx){if(!l[x]){sz[x]1;return;}dfs(l[x]);dfs(r[x]);sz[x]sz[l[x]]sz[r[x]]1;}voiddfs2(intx){ans[x]ans[fa[x]]2*sz[x]-1,ans[x]%mod;if(!l[x])return;dfs2(l[x]);dfs2(r[x]);}voidsolve(){cinn;fa[1]0;for(inti1;in;i){cinl[i]r[i];if(l[i])fa[l[i]]fa[r[i]]i;}dfs(1);ans[0]0;dfs2(1);for(inti1;in;i){coutans[i] ;}cout\n;}signedmain(){ios::sync_with_stdio(0);ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);intt1;cint;while(t--){solve();}return0;}