- 给定一张(n)个点的(DAG)。
- 求对于每一个点，有多少点被它支配。
- (nle65534,mle10^6)
支配树
支配树看起来很高级，实际上也的确很高级。。。
但这道题仅仅是(DAG)上的支配树，那就非常水了。
考虑求出每个点最低的支配祖先(fa_i)，显然一个点的支配祖先能支配所有这个点的支配后代。
而一个点的支配祖先就是它所有前驱节点的支配祖先在支配树上的(LCA)。
最后的询问就是求每个点在支配树上的子树大小，直接从后往前扫一遍拓扑队列就好了。
一个注意点是要建超级根，把(DAG)上不同的入度为(0)的点连接起来，不然就会建出一个奇怪的东西。
代码
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 65534
#define LN 18
#define M 1000000
#define add(x,y) (e[++ee].nxt=lnk[x],++deg[e[lnk[x]=ee].to=y])
using namespace std;
int n,ee,lnk[N+5],deg[N+5];struct edge {int to,nxt;}e[M+N+5];
class DominatingTree//支配树
{
private:
int q[N+5],sz[N+5],d[N+5],fa[N+5][LN+1];
I int LCA(RI x,RI y)//支配树上LCA
{
if(!~x) return y;RI i;d[x]<d[y]&&(x^=y^=x^=y);
for(i=0;d[x]^d[y];++i) ((d[x]^d[y])>>i)&1&&(x=fa[x][i]);if(x==y) return x;
for(i=LN;~i;--i) fa[x][i]^fa[y][i]&&(x=fa[x][i],y=fa[y][i]);return fa[x][0];
}
public:
I void Build()//拓扑建支配树
{
RI i,H=1,T=1,k,t;for(q[1]=0,i=1;i<=n;++i) fa[i][0]=-1,!deg[i]&&(add(0,i),0);W(H<=T)//以0为超级根
{
for(k=q[H++],d[k]=d[fa[k][0]]+1,i=1;i<=LN;++i) fa[k][i]=fa[fa[k][i-1]][i-1];//预处理倍增数组
for(i=lnk[k];i;i=e[i].nxt) !--deg[t=e[i].to]&&(q[++T]=t),fa[t][0]=LCA(fa[t][0],k);//访问后继节点，更新其支配祖先
}
for(i=T;i;--i) sz[fa[q[i]][0]]+=++sz[q[i]];for(i=1;i<=n;++i) printf("%d
",sz[i]-1);//倒扫一遍拓扑队列求支配子树大小
}
}T;
int main()
{
RI i,x;for(scanf("%d",&n),i=1;i<=n;++i) W(scanf("%d",&x),x) add(x,i);
return T.Build(),0;
}