Codeforces Round #695 (Div. 2) E. Distinctive Roots in a Tree(思维题-树上差分)

题目

n(n<=2e5)个点的树，点i有点权ai(1<=ai<=1e9)

"不同根"定义为，从该点出发，到任意点的路径上都不会经历两个相同的值

求图中"不同根"的个数

思路来源

凡神代码

题解

考虑到对于树上任意两个相同的值来说，

这两个点之外的点，都是不合法的点，

所以检查每两两个点即可，但是复杂度不符合要求

画画图发现，对于每个点来说，检查离它最近的相同的值的点即可

任选树根，对树进行dfs，记录dfs序，

对于点u来说，如果子树v里面存在和u相同的值，则需要对v子树以外的区间打+1标记

对于点u来说，如果子树u外存在和u相同的值，则需要对u子树内的区间打+1标记

一个点被打了多个标记是没关系的，只要保证合法的点没被打上标记即可

最后求一遍前缀和，统计没有标记的点的个数

对于判断u子树外和v子树内有没有和a[u]相同的值，

也可以启发式合并上来做，但感觉背离了这个思维题的初衷

代码

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=2e5+10;
map<int,int>to;
vector<int>e[N];
int n,a[N],u,v,x,ans;
int in[N],out[N],c;
int add,sum[N];
int up[N],cnt[N];
void dfs(int u,int fa){
	in[u]=++c;
	int pre=cnt[a[u]];
	for(auto &v:e[u]){
		if(v==fa)continue;
		int ppre=cnt[a[u]];
		dfs(v,u);
		int nnow=cnt[a[u]];
		if(nnow-ppre>0){//v子树有a[u] 对区间[in[v],out[v]]以外的区间打标 
			sum[1]++;
			sum[in[v]]--;
			sum[out[v]+1]++; 
		}
	}
	out[u]=c;
	cnt[a[u]]++;
	int now=cnt[a[u]];
	if(now-pre<up[a[u]]){//子树外有a[u] 对区间[in[u],out[u]]打标 
		sum[in[u]]++;
		sum[out[u]+1]--;
	}	
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		if(!to.count(a[i])){
			to[a[i]]=++x;
		}
	}
	for(int i=1;i<=n;++i){
		a[i]=to[a[i]];
		up[a[i]]++;
	}
	for(int i=1;i<n;++i){
		scanf("%d%d",&u,&v);
		e[u].pb(v);e[v].pb(u);
	}
	dfs(1,-1);
	for(int i=1;i<=n;++i){
		add+=sum[i];
		if(!add){
			ans++;
		} 
	}
	printf("%d\n",ans);
    return 0;
}