D. MEX Tree

一些我不会做的题,加上没有正常题解...就会变得very hard.

其实并没有多难.

这个先容斥一下,然后lca分三种情况讨论就好了.

贴个智商代码:

using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int mod=1e9+7;
const int N=2e5+5;
const int M=21;

int p[N],sz[N];
ll ans[N];
bool vis[N];//是不是在这个链上啊. 
vector<int>G[N];

void dfs(int u,int fa)
{
	sz[u]=1;p[u]=fa;
	for(int v:G[u])
	{
		if(v==fa)	continue;
		dfs(v,u);
		sz[u]+=sz[v];
	}
}

void run()
{
	int n;
	scanf("%d",&n);
	for(int i=0;i<=n+1;i++)	vis[i]=ans[i]=0,G[i].clear();
	for(int i=1;i<n;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	ans[0]=1ll*n*(n-1)/2;
	dfs(0,-1);
	ll tot=1;
	for(int v:G[0])
	{
		ans[1]+=tot*sz[v];
		tot+=sz[v];
	}
	int l=0,r=0;vis[0]=true;
	for(int i=1;i<n;i++)
	{
		if(!vis[i])
		{
			int now=i,son=-1;
			while(!vis[now])
			{
				vis[now]=true;
				son=now;
				now=p[now];
			}
			if(now==l)
			{
				sz[l]-=sz[son];
				l=i;
			}
			else if(now==r)
			{
				sz[r]-=sz[son];
				r=i;
			}
			else	break;
		}
		ans[i+1]=1ll*sz[l]*sz[r];
	}
	for(int i=0;i<=n;i++)
	{
		printf("%lld ",ans[i]-ans[i+1]);
	}
	puts("");
}
 
int main()
{
	int T=1;
	scanf("%d",&T);
	while(T--)	run(); 
	return 0;
}
/*
4
10 7 6 7

2
*/