网站更换服务器 备案,网站支付端口,对网站建设的建议,临沂做企业网站灾难 【样例输入】 5 0 1 0 1 0 2 3 0 2 0 【样例输出】 4 1 0 0 0 题解#xff1a; 先跑出拓扑序 我们按拓扑序建立一棵“灭绝树” 灭绝树含义是当一个点灭绝时#xff0c;它的子树将会全部灭绝 所以答案就是点在灭绝树中的子树大小 一个点如果灭绝#xff0c;那么需要所有… 灾难 【样例输入】 5 0 1 0 1 0 2 3 0 2 0 【样例输出】 4 1 0 0 0 题解 先跑出拓扑序 我们按拓扑序建立一棵“灭绝树” 灭绝树含义是当一个点灭绝时它的子树将会全部灭绝 所以答案就是点在灭绝树中的子树大小 一个点如果灭绝那么需要所有指向它的点灭绝 由于拓扑序的关系指向它的点已经加入过了灭绝树”中 所以这个点要灭绝就需要所有指向它的点全部灭绝即这些点的最近公共祖先 那么直接我们将这个祖先与此点连边更新Lca 最后求出子树大小即统计答案 1 #includealgorithm2 #includeiostream3 #includecstring4 #includecstdlib5 #includecstdio6 #includecmath7 using namespace std;8 inline int Get()9 {10 int x 0;11 char c getchar();12 while(0 c || c 9) c getchar();13 while(0 c c 9)14 {15 x (x 3) (x 1) c - 0;16 c getchar();17 }18 return x;19 }20 const int me 1000233;21 int n;22 int head, tail;23 int in[me];24 int ue[me];25 int de[me];26 int si[me];27 int fat[me][21];28 int tot, nex[2][me], fir[2][me], to[2][me];29 inline void Ins(int x, int y, int z)30 {31 nex[z][tot] fir[z][x];32 fir[z][x] tot;33 to[z][tot] y;34 }35 inline void Topo()36 {37 head 0, tail 0;38 for(int i 1; i n; i)39 if(!in[i])40 ue[tail] i;41 while(head tail)42 {43 int u ue[head];44 for(int i fir[0][u]; i; i nex[0][i])45 {46 int v to[0][i];47 --in[v];48 if(!in[v]) ue[tail] v;49 }50 }51 }52 inline int Lca(int x, int y)53 {54 if(x 0) return y;55 if(de[x] de[y]) swap(x, y);56 for(int i 20; i 0; --i)57 if(de[fat[x][i]] de[y])58 x fat[x][i];59 for(int i 20; i 0; --i)60 if(fat[x][i] ! fat[y][i])61 {62 x fat[x][i];63 y fat[y][i];64 }65 if(x y) return x;66 return fat[x][0];67 }68 inline void Update(int u, int v)69 {70 fat[v][0] u;71 de[v] de[u] 1;72 for(int i 1; i 20; i)73 fat[v][i] fat[fat[v][i - 1]][i - 1];74 }75 inline void Build()76 {77 while(tail)78 {79 int u ue[tail];80 int lca -1;81 for(int i fir[0][u]; i; i nex[0][i])82 {83 int v to[0][i];84 lca Lca(lca, v);85 }86 if(lca 0) lca 0;87 Ins(lca, u, 1);88 Update(lca, u);89 --tail;90 }91 }92 void Ergo(int u)93 {94 si[u] 1;95 for(int i fir[1][u]; i; i nex[1][i])96 {97 int v to[1][i];98 Ergo(v);99 si[u] si[v];
100 }
101 }
102 int main()
103 {
104 n Get();
105 for(int i 1; i n; i)
106 {
107 int x Get();
108 while(x)
109 {
110 in[x];
111 Ins(i, x, 0);
112 x Get();
113 }
114 }
115 Topo();
116 Build();
117 Ergo(0);
118 for(int i 1; i n; i)
119 printf(%d\n, si[i] - 1);
120 } 转载于:https://www.cnblogs.com/lytccc/p/6253270.html
