admin管理员组文章数量:1622629
题目链接
题意:给定一棵带点权无根树, 定义good root:good root到叶子节点任意一条路径上,都不包含相同元素。 问有多少个good root。
分析:参考大佬解法
我们先看相同的两个点
×的两个点权值相同,只会影响以它们为根的两棵树 。
我们需要把这两棵树所有节点都打上标记 ,所以我们可以跑一个dfs序 ,然后树的修改就变成区间修改了 ,方便用差分数组维护。
(跑dfs序需要根,我们可以令1为根。)
每对同权节点有两种情况:1、祖孙关系 2、非祖孙关系
-
对于2:我们dfs完以u为根的树的时候,如果发现除了u树外还有a[u] ,那么把u树全部打上标记就ok了。
-
对于1:参考下图
A的子树S中存在节点B与A权值相同,那么我们应该要把B子树全部修改+1,同时S子树之外的所有节点也全部修改+1。大佬的实现方法非常巧妙,我们不管B子树的修改,因为B子树的修改会在第一种情况中出现,只需要把S子树外的节点修改即可。
综合一下,具体的做法就是:
1、dfs完以u为根的树的时候,如果a[u]的个数小于总的a[u]个数,那么把u树全部标记
2、在u的dfs过程中,发现u的v子树中还有节点点权等于a[u],那么就标记v子树以外的全部的点 。
PS:标记v子树外全部的点,方法就是修改 [1,in[v]-1],[out[v]+1,n]这两个区间,
因为v子树dfs序区间为[in[v],out[v]]
最终差分数组统计前缀和,0代表没有被标记 ,满足good root。
#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(2)
#define ull unsigned long long
#define ll long long
#define pii pair<int, int>
const int maxn = 2e5 + 10;
const ll mod = 1e9 + 7;
const ll inf = (ll)4e16+5;
const int INF = 1e9 + 7;
const double pi = acos(-1.0);
ll inv(ll b){while(b==1)return 1;return(mod-mod/b)*inv(mod%b)%mod;}
inline ll read()
{
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){while(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n;
int a[maxn];
vector<int> g[maxn];
int in[maxn],clk,sz[maxn];
map<int,int> mp,now;
int d[maxn];
void dfs1(int rt,int f)
{
in[rt]=++clk;
sz[rt]=1;
now[a[rt]]++;//dfs到当前位置的点权记录
int temp=now[a[rt]];
int cnt=1;//当前子树中a[rt]的数量
for(int i:g[rt])
{
if(i==f) continue;
dfs1(i,rt);
sz[rt]+=sz[i];
if(now[a[rt]] > temp) //i子树中有a[rt] [in[i],out[i]]之外的区间都+1
{
d[1]++,d[in[i]]--;
d[in[i]+sz[i]]++,d[n+1]--;
}
cnt+=(now[a[rt]]-temp);
temp=now[a[rt]];
}
if(mp[a[rt]]>cnt) //rt子树之外还有a[rt]
{
//in[rt],out[rt]
d[in[rt]]++;
d[in[rt]+sz[rt]]--;
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",a+i),mp[a[i]]++;
for(int i=1,u,v;i<n;i++)
{
scanf("%d %d",&u,&v);
g[u].push_back(v);
g[v].push_back(u);
}
dfs1(1,0);
int ans=0;
for(int i=1;i<=n;i++)
{
d[i]+=d[i-1];
ans+=(!d[i]);
}
cout<<ans<<'\n';
return 0;
}
本文标签: 组合差分treeRootsdistinctive
版权声明:本文标题:Distinctive Roots in a Tree CodeForces - 1467E (组合优化+dfs序 +差分) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dongtai/1728870439a1177213.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论