免费网站推广平台排行榜,搜索引擎网站录入,wordpress 手工网站,好口碑关键词优化地址E. Distinctive Roots in a Tree
树上差分 如果当前节点u的某一棵子树中的某个节点的值和当前节点相同#xff0c;那么除了当前节点这一棵子树节点#xff0c;其他节点#xff08;其他子树以及u上面的节点#xff09;一定不满足要求。 如果当前节点子树之外的节点#x…E. Distinctive Roots in a Tree
树上差分 如果当前节点u的某一棵子树中的某个节点的值和当前节点相同那么除了当前节点这一棵子树节点其他节点其他子树以及u上面的节点一定不满足要求。 如果当前节点子树之外的节点u上面的节点与当前节点值相同那么当前子树节点不满足要求。
如何知道当前子树中的节点是否与当前节点相同 dfs过程中记录进入该子树之前某值的个数与出子树后该值的个数进行比较如果比之前多说明子树中存在该值。
如何知道当前节点所有子树之外的节点是否存在与当前值相同的节点? 如果不存在说明当前节点所有子树出现该值个数和应该与总个数相同
对于不能作为答案的节点标记一下即可由于只有子树操作考虑dfs序区间修改单点查询差分即可。
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#includeset
#includemap
#includecmath
#includestack
#includequeue
#includerandom
#includebitset
#includestring
#includevector
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#includeunordered_map
#includeunordered_set
using namespace std;
typedef long long ll;
typedef pairint,int pii;
const int N200010,mod1e97;
int h[N],e[2*N],ne[2*N],idx;
int a[N],cnt[N],num[N],s[N],n;
mapint,int mp;
int find(int x)
{if(!mp.count(x)) mp[x]idx;return mp[x];
}
void add(int a,int b)
{e[idx]b,ne[idx]h[a],h[a]idx;
}
void update(int l,int r,int x)
{s[l]x,s[r1]-x;
}
int dfn[N],timestamp,sz[N];
void dfs(int u,int fa)
{dfn[u]timestamp;sz[u]1;int nowcnt[a[u]];// 差分统计u子树出现a[u]的次数cnt[a[u]];for(int ih[u];i!-1;ine[i]){int je[i];if(jfa) continue;int precnt[a[u]];//进入子树前dfs(j,u);sz[u]sz[j];if(cnt[a[u]]pre) //说明j子树出现了a[u]update(1,n,1),update(dfn[j],dfn[j]sz[j]-1,-1);}if(cnt[a[u]]-now!num[a[u]])//差分统计u子树出现a[u]的次数 不等于总个数update(dfn[u],dfn[u]sz[u]-1,1);//1表示不能作为答案}
int main()
{IO;int T1;//cinT;while(T--){memset(h,-1,sizeof h);cinn;for(int i1;in;i) {cina[i];a[i]find(a[i]);num[a[i]];//总个数}idx0;for(int i1;in;i){int a,b;cinab;add(a,b),add(b,a);}dfs(1,-1);int res0;for(int i1;in;i){s[i]s[i-1];if(!s[i]) res;}coutres\n;}return 0;
}要加油哦~
