宿迁做网站 宿迁网站建设/seo是什么职业做什么的

题目

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;
}