admin管理员组文章数量:1622541
//如果上面有与根节点一样的点,整颗子树不考虑//如果子树内有与根节点一样的点,只考虑那个子树,同时上面的所有点不考虑//如果有两颗子树存在与根节点一样的点,直接NO//如果上下都不存在,正常往下搜//现在问题转化为,怎么求每个子树是否存在与根节点一样的点//离散化+维护一个dfs序即可//对dfs序用可持久化线段树维护区间内是否存在相同的点//事先算一遍每种颜色的点出现了多少次//用可持久化线段树维护区间内对应颜色点的出现次数
#include
using namespacestd;const int maxn=2e5+100;const int M=maxn*40;
vectorg[maxn];intn,m,q,a[maxn],t[maxn],T[maxn];intlson[M];intrson[M];intc[M];inttot;int build (int l,intr) {int root=tot++;
c[root]=0;if (l!=r) {int mid=(l+r)>>1;
lson[root]=build(l,mid);
rson[root]=build(mid+1,r);
}returnroot;
}int up (int root,int p,intv) {int newRoot=tot++;int tmp=newRoot;int l=1,r=m;
c[newRoot]=c[root]+v;while (l>1;if (p<=mid) {
lson[newRoot]=tot++;
rson[newRoot]=rson[root];
newRoot=lson[newRoot];
root=lson[root];
r=mid;
}else{
rson[newRoot]=tot++;
lson[newRoot]=lson[root];
newRoot=rson[newRoot];
root=rson[root];
l=mid+1;
}
c[newRoot]=c[root]+v;
}returntmp;
}int query (int left_root,int right_root,int l,int r,int L,intR) {if (l>=L&&r<=R) return c[left_root]-c[right_root];int mid=(l+r)>>1;int ans=0;if (L<=mid) ans+=query(lson[left_root],lson[right_root],l,mid,L,R);if (R>mid) ans+=query(rson[left_root],rson[right_root],mid+1,r,L,R);returnans;
}int cnt[maxn];//保存每个点的总共出现次数
int id[maxn];//保存dfs序
int size[maxn];//保存子树大小
int tol=0;//用于标记
intcol[maxn];void dfs (int x,intf) {
size[x]=1;
id[x]=++tol;
col[tol]=a[x];
cnt[a[x]]++;for (inty:g[x]) {if (y==f) continue;
dfs(y,x);
size[x]+=size[y];
}
}int cf[maxn];//树上差分数组
void dfs1 (int x,intf) {//printf("%d %d %d\n",x,cnt[a[x]],query(T[id[x]],T[id[x]+size[x]],1,m,a[x],a[x]));
if (cnt[a[x]]>query(T[id[x]],T[id[x]+size[x]],1,m,a[x],a[x])&&query(T[id[x]],T[id[x]+size[x]],1,m,a[x],a[x])>1) {
printf("0\n");
exit(0);
}if (cnt[a[x]]>query(T[id[x]],T[id[x]+size[x]],1,m,a[x],a[x])) {
cf[id[x]]++;
cf[id[x]+size[x]]--;
}int tt=0;for (inty:g[x]) {if (y==f) continue;if (query(T[id[y]],T[id[y]+size[y]],1,m,a[x],a[x])) tt++;
}//printf("%d %d\n",x,tt);
if (tt>1) {
printf("0\n");
exit(0);
}if (!tt) {for (inty:g[x]) {if (y==f) continue;
dfs1(y,x);
}
}else{
cf[1]++;
cf[n+1]--;for (inty:g[x]) {if (y==f) continue;if (query(T[id[y]],T[id[y]+size[y]],1,m,a[x],a[x])) {
cf[id[y]]--;
cf[id[y]+size[y]]++;
}
dfs1(y,x);
}
}
}intmain () {
scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",a+i),t[i]=a[i];
sort(t+1,t+n+1);
m=unique(t+1,t+n+1)-t-1;for (int i=1;i<=n;i++) a[i]=upper_bound(t+1,t+m+1,a[i])-t-1;for (int i=1;i
scanf("%d%d",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
}
dfs(1,0);
T[n+1]=build(1,m);for (int i=n;i>=1;i--) T[i]=up(T[i+1],col[i],1);
dfs1(1,0);//dfs1(n,0);
int Ans=0;int sum=0;for (int i=1;i<=n;i++) {
sum+=cf[i];//printf("%d\n",sum);
if (!sum) Ans++;
}
printf("%d\n",Ans);
}
版权声明:本文标题:mysql 1467_1467E. Distinctive Roots in a Tree(可持久化线段树+树上差分) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/dianzi/1728870471a1177217.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论