D.MEX Tree
题意：
给出一棵树，下标0到n-1。
对从0到n的每个k，求出有多少条路径MEX=k。
题解：
树上分类讨论+容斥
首先容斥计算0的答案，有多少条路径不包含0？
答案是取出0的所有相邻节点，他们内部的子树的路径数量加起来。
然后容斥计算1的答案，有多少条路径包含0不包含1？
所有经过0的路径减去经过01的路径，经过01的路径数量就是先确定01的位置，然后求出0相对于1的子树大小x和1相对于0的子树大小y，xy就是答案。这里x相对于y的子树或y相对于x的子树在下文统称相对子树。
然后从2开始计算答案。
假设当前计算的点是x。
我们要求有多少条路径包含0到x-1，却不包含x。
用A，B表示包含0到x-1的路径的最短路径的起点和终点。
如果x在A或B的相对子树内，直接将A或B的相对子树大小减去i的子树大小，根据01路径的计算方法求一遍即可，然后把A或B更新为i即可。
如果i在A到B的路径上，那么i的答案注定是0。因为要构造包含0到i-1的路径，必定会经过i。
如果i既不在A或B的相对子树内，也不在A到B的路径上，当前的答案就是A的相对子树大小乘上B的相对子树，同时后面所有路径都无法构造。
时间复杂度(O(nlogn))。
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*f;
}
const int maxn=2e5+100;
int t,n;
int sz[maxn];
int dfn[maxn];
int tot=0;
vector<int> g[maxn];
int father[30][maxn];
int h[maxn];
void dfs (int x,int pre) {
sz[x]=1;
dfn[x]=++tot;
for (int y:g[x]) {
if (y==pre) continue;
h[y]=h[x]+1;
father[0][y]=x;
dfs(y,x);
sz[x]+=sz[y];
}
}
int lca (int x,int y) {
if (h[x]<h[y]) swap(x,y);
for (int i=20;i>=0;i--) {
if (h[x]-h[y]>>i) x=father[i][x];
}
if (x==y) return x;
for (int i=20;i>=0;i--) {
if (father[i][x]!=father[i][y]) {
x=father[i][x];
y=father[i][y];
}
}
return father[0][x];
}
int main () {
t=read();
while (t--) {
n=read();
tot=0;
for (int i=0;i<=20;i++) for (int j=0;j<n;j++) father[i][j]=0;
for (int i=0;i<n;i++) g[i].clear(),h[i]=0;
for (int i=1;i<n;i++) {
int x=read();
int y=read();
g[x].push_back(y);
g[y].push_back(x);
}
dfs(0,-1);
for (int i=1;i<=20;i++) for (int j=0;j<n;j++) father[i][j]=father[i-1][father[i-1][j]];
//容斥计算0的答案
//就是0的所有子树内部算一下路径即可
long long ans=0;
for (int y:g[0]) {
ans+=1ll*sz[y]*(sz[y]-1)/2;
}
printf("%lld ",ans);
//容斥计算1的答案
//就是所有经过0的路径减去经过01的路径
//1子树内的点不考虑即可
ans=0;
long long sum=1;
int fa=-1;
for (int y:g[0]) {
int x=sz[y];
if (dfn[1]>=dfn[y]&&dfn[1]<=dfn[y]+sz[y]-1) {
//如果1在y的子树内
fa=y;
x-=sz[1];
}
ans+=1ll*x*sum;
sum+=x;
}
printf("%lld ",ans);
int A=0,B=1;//AB分别表示之前路径的起点和终点
//fa表示如果A为0，B在A的哪个子树
for (int i=2;i<=n;i++) {
//计算mex=i的答案
//如果i==n
if (i==n) {
printf("1 ");
break;
}
//先讨论i的位置
//i在B的子树内
if (dfn[i]>=dfn[B]&&dfn[i]<=dfn[B]+sz[B]-1) {
ans=0;
long long x,y;
if (A==0) {
x=n-sz[fa];
}
else {
x=sz[A];
}
y=sz[B]-sz[i];
ans=1ll*x*y;
printf("%lld ",ans);
B=i;
}
else {
//如果i在A的子树内
if (A==0&&(dfn[i]<dfn[fa]||dfn[i]>dfn[fa]+sz[fa]-1)) {
ans=0;
long long x,y;
x=n-sz[fa]-sz[i];
y=sz[B];
ans=1ll*x*y;
printf("%lld ",ans);
A=i;
}
else if (A!=0&&dfn[i]>=dfn[A]&&dfn[i]<=dfn[A]+sz[A]-1) {
ans=0;
long long x,y;
x=sz[A]-sz[i];
y=sz[B];
ans=1ll*x*y;
printf("%lld ",ans);
A=i;
}
//如果i在A到B的路径上
//答案是0
else if (lca(A,i)==i||lca(B,i)==i) {
ans=0;
printf("%lld ",ans);
}
//如果不在
//答案是包含A到B的路径的路径数量
//
else {
long long x,y;
ans=0;
if (A==0) x=n-sz[fa];
else x=sz[A];
y=sz[B];
ans=1ll*x*y;
printf("%lld ",ans);
for (int j=i+1;j<=n;j++) printf("0 ");
break;
}
}
}
printf("
");
}
}