CF1467E Distinctive Roots in a Tree 树上差分 dfs序

admin管理员组

文章数量:1622631

题目链接

题意：
给你一个 n n n个点的无根树，每个点有点权，问你有多少个点满足以它为根的树中每一条根到叶子的路径上都没有权值相同的点。
n < = 2 e 5 ， 点 权 < = 1 e 9 n<=2e5，点权<=1e9 n<=2e5，点权<=1e9

题解：
智商又掉线了，想了一堆树链剖分、主席树和dfs序的东西，然后发现都不对。最后结果是树上差分就行了。

这题肯定要先对权值离散化。

首先这个题你尝试去维护或者算信息时会发现，想要通过一些信息来算出合法点是不太容易的，但是我们标记不合法点是相对容易的。所以基于这个想法，我们把不合法点标记，所有没被标记的点就是合法点。

由于 n < = 2 e 5 n<=2e5 n<=2e5，所以我们通常的想法是随便找一个点为根来dfs，在dfs的过程中处理出换根时要用的信息。

在从上向下dfs过程中我们考虑什么样的点是不合法的。以下说的子树都是不包括换根后向上的那个子树的。我们把不合法情况分为两类。

第一类：如果对于一个点，所有与它权值相同的点如果没有全部出现在它的子树里，那么它所在的子树里的所有点为根一定都是不合法的，一定有一条路径会经过当前点和向随便指定的根的方向的某个权值与当前点相同的点。

第二类：
如果对于当前dfs的点 x x x，它的某一个儿子所在的子树里出现了与点 x x x权值相同的点，那么其他子树与连向根的那个子树就一定不合法。那么我们就把除了这个儿子所在的子树外的点都标记。

打标记的方法是求一个dfs序，然后对于一个区间打差分标记，因为和轻重链没什么关系，所以用不着树链剖分了。

最后对于差分数组求前缀和来判断是否有标记来累加答案就可以了。

代码：

#include <bits/stdc++.h>
using namespace std;

int n,v[200010],hed[400010],cnt,b[200010],m;
int num,f[200010],xu[200010],ed[200010];
int tong[200010],ans,s[200010],ss[200010];
struct node
{
	int to,next;
}a[800010];
struct tree
{
	int l,r,sum;
}tr[4000010];
inline void add(int from,int to)
{
	a[++cnt].to=to;
	a[cnt].next=hed[from];
	hed[from]=cnt;
}
inline void dfs(int x)
{
	xu[x]=++num;
	int ji1=ss[v[x]];
	++ss[v[x]];
	for(int i=hed[x];i;i=a[i].next)
	{
		int y=a[i].to;
		if(y==f[x])
		continue;
		int ji2=ss[v[x]];
		f[y]=x;
		dfs(y);
		if(ss[v[x]]>ji2)//×ÓÊ÷ÄÚÓÐÕâ¸öÊý£¬ÄÇôÆäËû×ÓÊ÷¶¼²»ºÏ·¨
		{
			s[1]++;
			s[xu[y]]--;
			s[ed[y]+1]++;
		}
	}
	ed[x]=num;
	if(ss[v[x]]-ji1<tong[v[x]])//×ÓÊ÷ÍâÓÐÕâ¸öÊý£¬×ÓÊ÷ÄڵĶ¼²»ºÏ·¨ 
	{
		s[xu[x]]++;
		s[ed[x]+1]--;
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&v[i]);
		b[i]=v[i];	
	}
	for(int i=1;i<=n-1;++i)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}
	sort(b+1,b+n+1);
	m=unique(b+1,b+n+1)-b-1;
	cnt=0;	
	for(int i=1;i<=n;++i)
	{
		v[i]=lower_bound(b+1,b+m+1,v[i])-b;
		tong[v[i]]++;
	}
	dfs(1);
	for(int i=1;i<=n;++i)
	{
		s[i]=s[i-1]+s[i];
		if(s[i]==0)
		++ans;
	}
	printf("%d\n",ans);
	return 0;
}

本文标签： 树上差分distinctiveCF1467ERoots