Codeforces-1467 E. Distinctive Roots in a Tree（dfs序，树上差分）

admin管理员组

文章数量:1622542

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