传送门

题意：给你一颗树，每个节点都有一个标号，问你将一个节点所有子节点及其本身的标号连接能形成几段。

题解：大多是用线段树合并写的，所以补一发主席树的做法。将树用dfs序hash下来后，对于每一个节点，我们可以得知如果当前节点的前继在当前掌控的范围那么段数会减少一，即当前节点可以和子树中的节点合并为一段，那么问题就转化为对于当前节点掌控的子树，子节点中有多少节点的前驱在掌控范围中，这个就是主席树的基本操作了。

代码：

#include<stdio.h>
#include<vector>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<math.h>
#include<queue>
#include<set>
#include<map>
#include<stack>
#define ll long long
#define fo(n) for(int i=1;i<=n;i++)
#define fol(n) for(int i=n;i>=1;i--)
#define foj(i,n) for(int j=i;j<=n;j++)
#define fok(i,j) for(int k=i;k<=j;k++)
#define oui(i) printf("%d\n",i)
#define oul(i) printf("%lld\n",i)
#define sc(n) scanf("%d",&n)
#define scl(n) scanf("%lld",&n)
#define mid ((l+r)>>1)
#define ls k<<1
#define rs (k<<1)+1
using namespace std;
int read(){char c;int x=0,y=1;while(c=getchar(),(c<'0'||c>'9')&&c!='-');if(c=='-') y=-1;else x=c-'0';while(c=getchar(),c>='0'&&c<='9')x=x*10+c-'0';return x*y;
}
const int maxn=2e5+10;
const int inf=1e7;
int lk[maxn*60],rk[maxn*60],num[maxn*60];
struct node{int to,next;
};
node side[maxn*2];
int head[maxn],tot,ti[maxn];
int in[maxn],out[maxn],wi[maxn],sz[maxn];
void add_edge(int u,int v){side[tot].to=v;side[tot].next=head[u];head[u]=tot++;
}
void dfs(int now,int fa){in[now]=++tot;wi[tot]=now;sz[now]=1;for(int i=head[now];i!=-1;i=side[i].next){int v=side[i].to;if(v==fa) continue;dfs(v,now);sz[now]+=sz[v];}out[now]=tot;
}
void add(int last,int &now,int l,int r,int w1){now=++tot;num[now]=num[last]+1;lk[now]=lk[last];rk[now]=rk[last];if(l==r) return ;if(mid>=w1) add(lk[last],lk[now],l,mid,w1);else add(rk[last],rk[now],mid+1,r,w1);
}
int query(int las,int now,int l,int r,int l1,int r1){if(l>=l1&&r<=r1) return num[now]-num[las];if(mid>=r1) return query(lk[las],lk[now],l,mid,l1,r1);else if(mid+1<=l1) return query(rk[las],rk[now],mid+1,r,l1,r1);else return query(lk[las],lk[now],l,mid,l1,r1)+query(rk[las],rk[now],mid+1,r,l1,r1);
}
int main( ){lk[0]=rk[0]=num[0]=ti[0]=0;in[0]=1;int t=read();for(int i=1;i<=t;i++){int n=read();for(int a=1;a<=n;a++) head[a]=-1;tot=0;for(int a=1;a<n;a++){int u=read(),v=read();add_edge(u,v);add_edge(v,u);}tot=0;dfs(1,1);for(int a=1;a<=n;a++)add(ti[a-1],ti[a],1,n,in[wi[a]-1]);printf("Case #%d: 1",i);for(int a=2;a<=n;a++)printf(" %d",sz[a]-query(ti[in[a]-1],ti[out[a]],1,n,in[a],out[a]));printf("\n");}
}