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) #include<set> #include<map> #include<cmath> #include<stack> #include<queue> #include<random> #include<bitset> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<unordered_map> #include<unordered_set> using namespace std; typedef long long ll; typedef pair<int,int> pii; const int N=200010,mod=1e9+7; int h[N],e[2*N],ne[2*N],idx; int a[N],cnt[N],num[N],s[N],n; map<int,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[r+1]-=x; } int dfn[N],timestamp,sz[N]; void dfs(int u,int fa) {dfn[u]=++timestamp;sz[u]=1;int now=cnt[a[u]];// 差分統計u子樹出現a[u]的次數cnt[a[u]]++;for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];if(j==fa) continue;int pre=cnt[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 T=1;//cin>>T;while(T--){memset(h,-1,sizeof h);cin>>n;for(int i=1;i<=n;i++) {cin>>a[i];a[i]=find(a[i]);num[a[i]]++;//總個數}idx=0;for(int i=1;i<n;i++){int a,b;cin>>a>>b;add(a,b),add(b,a);}dfs(1,-1);int res=0;for(int i=1;i<=n;i++){s[i]+=s[i-1];if(!s[i]) res++;}cout<<res<<'\n';}return 0; }

要加油哦~

總結

以上是生活随笔為你收集整理的codeforces1467 E. Distinctive Roots in a Tree（树上差分）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。