admin管理员组文章数量:1622626
Codeforces-1467 E. Distinctive Roots in a Tree(dfs序,树上差分)
https://codeforces/contest/1467/problem/E
题意:
一棵有点权的无根树,定义特殊点:该点到树上任意一点路径上的点权不重复。问特殊点的数量。
题解:
任取一个作为根节点。定义特殊值:只有特殊点的特殊值为0。我们考虑当前节点u 。树会被分成三个部分,点集A = { x ∣ d f n [ x ] < d f n [ u ] },也就是在u 之前已经遍历的点;点集B = { x ∣ x 是 u 子 树 上 的 节 点 } ;点集C = { x ∣ x ∉ A ∨ B } ,也就是还没遍历到的、不是u 子树的节点。
1.∃ x ∈ A ∨ C , a [ x ] = a [ u ] ,那么B中所有点的都不是特殊点。将u 子树上所有点特殊值加1。
2.∀ x ∈ A ∨ C , a [ x ] ≠ a [ u ] ; ∃ y ∈ B ∩ y ≠ u , a [ y ] = a [ u ] ,那么的y 所在的儿子子树中存在特殊点,且A 、C 和u 的其他所有儿子子树的所有点都不是特殊点。将树上所有点特殊值加1,再将y 所在这棵儿子子树的特殊值减1。因为在遍历到y 的时候,根据1. ,已经对y 的子树特殊值加1了,就实现了只有u 到y 中间的点特殊值没有改变。
观察发现,每一次的特殊值的改变都是以子树为单位进行的。树上差分。
对于1. 的实现,首先预处理出所有点权的出现次数mp1,用mp2在遍历的时候记录点权出现的次数。遍历到u的时候,可以记录一下tmp=mp2[a[u]],代表A中点权为a[u]的点的数量;遍历完u的子树后,此时mp2[a[u]]表示A ∨ B中a[u]的出现次数;那么mp2[a[u]]−tmp代表着B中a[u]的出现次数。如果mp2[a[u]]−tmp<mp1[a[u]],说明A ∨ C 中存在点权为a[u]的点,执行1. 。
代码 :
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cstdio>
using namespace std ;
typedef long long ll ;
const int maxn = 2e5 + 7 ;
const int mod = 1e9 + 7 ;
vector<int> vec , g[maxn] ;
int a[maxn] ;
int sum[maxn] , sta[maxn] , ed[maxn] , cnt ;
int num[maxn] ; //遍历过程每个数的出现次数
int mum[maxn] ; //初始每个数的出现次数
void dfs(int x , int fa){
sta[x] = ++cnt ;
int now_v = num[a[x]] ;
num[a[x]]++ ;
for(int i = 0 ; i < g[x].size() ; i++){
int v = g[x][i] ;
if(v == fa) continue ;
int pre = num[a[x]] ;
dfs(v , x) ;
if(num[a[x]] > pre){ //第二种情况
sum[1]++ ; //这个子树有a[x] , 则x以及其他子树的点都非法
sum[sta[v]]-- ;
sum[ed[v]+1]++ ;
}
}
ed[x] = cnt ;
if(num[a[x]] - now_v != mum[a[x]]){ //第一种情况
sum[sta[x]]++ ; //连向父节点的子树有a[x],那么x以及x对应其他子树非法
sum[ed[x]+1]-- ;
}
}
int main(){
int n ;
cin >> n ;
for(int i = 1 ; i <= n ; i++){
cin >> a[i] ;
vec.push_back(a[i]) ;
}
sort(vec.begin() , vec.end()) ;
vec.erase(unique(vec.begin() , vec.end()) , vec.end()) ;
for(int i = 1 ; i <= n ; i++){
a[i] = lower_bound(vec.begin() , vec.end() , a[i]) - vec.begin() ;
mum[a[i]]++ ;
}
for(int i = 1 ; i < n ; i++){
int x , y ;
cin >> x >> y ;
g[x].push_back(y) ;
g[y].push_back(x) ;
}
dfs(1 , -1) ;
int ans = 0 ;
for(int i = 1 ; i <= n ; i++){
sum[i] += sum[i-1] ;
if(sum[i] == 0)
ans++ ;
}
cout << ans << endl ;
return 0 ;
}
本文标签: 树上差分distinctivecodeforcesDFS
版权声明:本文标题:Codeforces-1467 E. Distinctive Roots in a Tree(dfs序,树上差分) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dianzi/1728870416a1177211.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论