[HNOI2014]世界树

• 题意：[HNOI2014]世界树
• 思路：
  首先建好虚树。（为了方便size的预处理，强制虚数里面的根为1）
  预处理出每个点最近的关键点bl,以及到它的距离。
  然后一条边上（不含两端）：(u->v)
  且设p为u的儿子中是v的祖先的。
  1.\(bl[u]=bl[v]:\ ans[bl[u]]=sz[p]-sz[v]\);
  2.\(bl[u]!=bl[v]:\ 一定存在一个点为bl[u]和bl[v]的分割点。倍增找就行了。找到点x\)。
  \(ans[bl[v]]+=sz[x]-sz[v]\)
  \(ans[bl[u]]+=sz[p]-sz[x]\)
  端点上的点：每个点要算的是它的所有满足子树内没有关键点的非虚数上的节点。
  很简单，我们容斥一下，用sz[u]减去所有的sz[p]记得多个v可能有相同的p要标记去重。
• code:

#include
using namespace std;
typedef long long ll;
const int N=3e5+5;
int tt[N],h[N],ans[N],sz[N],inf=1e9,dis[N],bl[N],st[N],tp,In[N],Out[N],Time,fa[N][21],nxt[N<<1],to[N<<1],head[N],dep[N],ecnt,lg[N],mark[N],dp[N],len[N<<1];
bool vis[N];
struct node {int p,dfn;}a[N];
bool cmp(node u,node v) {return u.dfn=0;i--) 
		if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
	return fa[u][0];
}
void dfs1(int u) {
	if(mark[u]==1) dis[u]=0,bl[u]=u;
	else dis[u]=inf;
	for(int i=head[u];i;i=nxt[i]) {
		int v=to[i];
		dfs1(v);
		if(mark[u]!=1) {
			if(dis[v]+len[i]bl[v]) bl[u]=bl[v];
		}
	}
}
void dfs2(int u) {
	ans[u]=0;
	for(int i=head[u];i;i=nxt[i]) {
		int v=to[i];
		if(mark[v]==2) {
			if(dis[u]+len[i]bl[u]) bl[v]=bl[u];
		}
		dfs2(v);
	}
//	printf("%d(%d): %d %d\n",u,mark[u],bl[u],dis[u]);
}
void solve(int u) {
	ans[bl[u]]+=sz[u];
//	printf("+[%d]%d %d(%d)\n",ans[bl[u]],bl[u],sz[u],u);
	int cc=0;
	for(int i=head[u];i;i=nxt[i]) {
		int v=to[i],p=v,k=dep[v]-dep[u]-1;
		for(int j=0;j<=lg[k];j++)if((1<=0;j--) {
			if(tmp>1]+1;
	for(int i=1;iOut[st[tp]]) tp--;
			add_edge(st[tp],u,dep[u]-dep[st[tp]]);
			st[++tp]=u;
		}
		dfs1(a[1].p);
		dfs2(a[1].p);
		solve(a[1].p);
		for(int i=1;i<=cc;i++) printf("%d ",ans[h[i]]);
		puts("");
		for(int i=1;i<=ct;i++) mark[a[i].p]=head[a[i].p]=vis[a[i].p]=0; ecnt=0;
	}
	return 0;
}