dus on tree学习笔记

前言

dus on tree 就像其实就像是暴力，但是通过选择正确的顺序，使得暴力变得更加的快速。

算法思路

给出一颗 n 个节点的树，每个节点有一个颜色，询问你没个节点的子树中有多少中颜色。

显然，我们知道暴力扫的话是枚举每个点，再暴力去找他的子树，显然在暴力的情况下是 \(O(n^2)\) 的。但我们发现，其实很多信息我们都会重复用到，如果每次都删除过于浪费，但如果直接保存的话又可能会影响到其他的子树。

所以我们要找到一个正确的顺序去保存，显然，我们可以在之后所有的节点都包括这颗子树的时候，就可以保存答案了。什么时候都保存呢？我们可以规定一个枚举顺序，规定某一条边必需最后访问，这样从上面递归到这条最后的边的时候，前面的边肯定都已经递归完了，所以我们就可以保存这颗子树的所有信息了。

我们发现这样最后最后一条边所在的子树会被访问1次，其他的会被访问2次，显然希望最后一条边所在的子树越大越好，所以就可以规定重边为最后一条边。

code

#include<bits/stdc++.h>
using namespace std;
const int N=100011;
int n;
int col[N];
struct node{
	int to,lt;
}e[N<<1];
int tot,last[N];
void add(int u,int v){
	e[++tot].lt=last[u];
	e[tot].to=v;
	last[u]=tot;
}
int sum;
int size[N],son[N],L[N],R[N],cnt,id[N];
void dfs1(int u,int fa){//找轻重边，dfs序 
	size[u]=1;
	L[u]=++cnt;
	id[cnt]=u;
	for(int i=last[u];i;i=e[i].lt){
		int v=e[i].to;
		if(v==fa)continue;
		dfs1(v,u);
		size[u]+=size[v];
		if(size[son[u]]<size[v])son[u]=v;
	}
	R[u]=cnt;
}
int a[N],ans[N];
void add(int u){//加减儿子，发没发现很想莫队
	a[col[u]]++;
	if(a[col[u]]==1)sum++;
}
void del(int u){//所以这玩意还有个名字叫子树莫队 
	a[col[u]]--;
	if(a[col[u]]==0)sum--;
}
void dfs2(int u,int fa,bool keep){//keep表示这条边要不要存 
	for(int i=last[u];i;i=e[i].lt){//先把亲儿子求完 
		int v=e[i].to;
		if(v==fa||v==son[u])continue;
		dfs2(v,u,false);
	}
	if(son[u])dfs2(son[u],u,true);//重儿子是要保存的 
	for(int i=last[u];i;i=e[i].lt){
		int v=e[i].to;
		if(v==fa||v==son[u])continue;
		for(int j=L[v];j<=R[v];j++)add(id[j]);
	}
	add(u);
	ans[u]=sum;
	if(keep==false){
		//注意是要把整颗子树的信息都删掉 
		for(int i=L[u];i<=R[u];i++)del(id[i]);
	}
	return ;
}
int m;
int main(){
	cin>>n;
	for(int i=1;i<=n-1;i++){
		int u,v;
		cin>>u>>v;
		add(u,v);
		add(v,u);
	}
	for(int i=1;i<=n;i++)cin>>col[i];
	dfs1(1,0);
	dfs2(1,1,false);
	cin>>m;
	for(int i=1;i<=m;i++){
		int k;
		cin>>k;
		cout<<ans[k]<<endl;
	}
}