本文共 3061 字，大约阅读时间需要 10 分钟。

You are given a tree with n vertices, numbered from 1 to n. ith vertex has a value wiwi

We define the weight of a tree as the number of different vertex value in the tree. If we delete one edge in the tree, the tree will split into two trees. The score is the sum of these two trees’ weights. We want the know the maximal score we can get if we delete the edge optimally Input Input is given from Standard Input in the following format: n p2p2 p3p3 . . . pnpn w1w1 w2w2 . . . wnwn Constraints 2 ≤ n ≤ 100000 1 ≤ pipi < i 1 ≤ wiwi ≤ 100000(1 ≤ i ≤ n), and they are integers pipi means there is a edge between pipi and i Output Print one number denotes the maximal score Sample Input 3 1 1 1 2 2 3 1 1 1 1 1 Sample Output 3 2 这个题好多题解是啥启发式合并，咱也看不懂，咱也不敢问。 我这个题是主席树做的。一开始想的是树上主席树，但是好像整不了。dfs序之后，所有的节点的顺序就知道了。我们断开一条边的时候，断开的那个子节点就是在他的子树里找不同数字的个数，那么形成的另一颗树呢，就是不连续的了。我们怎么样才能让它成为连续的。方法就是dfs之后形成的序列，都加一倍,即：123变为123123。这样形成的两颗子树在这组序列里都是连续的。树形结构也就转化成了线性结构。这就转化成了区间不同数字的个数。 代码如下：

#include
   
    #define ll long longusing namespace std;const int maxx=2e5+100;struct node{
   	int l;	int r;	int sum;}p[maxx*40];struct edge{
   	int to;	int next;}e[maxx<<1];int a[maxx],head[maxx<<1],in[maxx],out[maxx],root[maxx<<1],pre[maxx<<1];int n,tot,sign,ror;/*--------------事前准备----------------*/inline void init(){
   	memset(head,-1,sizeof(head));	tot=sign=ror=0;}inline void add(int u,int v){
   	e[tot].to=v,e[tot].next=head[u],head[u]=tot++;}/*---------------主席树---------------*/inline int build(int l,int r){
   	int cur=++ror;	p[cur].sum=0;	if(l==r) return cur;	int mid=l+r>>1;	p[cur].l=build(l,mid);	p[cur].r=build(mid+1,r);	return cur;}inline int update(int rot,int l,int r,int pos,int v){
   	int cur=++ror;	p[cur]=p[rot];	p[cur].sum+=v;	if(l==r) return cur;	int mid=l+r>>1;	if(pos<=mid) p[cur].l=update(p[rot].l,l,mid,pos,v);	else p[cur].r=update(p[rot].r,mid+1,r,pos,v);	return cur;}inline int query(int rot,int l,int r,int L,int R){
   	if(l<=L&&R<=r) return p[rot].sum;	int mid=L+R>>1;	int sum=0;	if(l<=mid) sum+=query(p[rot].l,l,r,L,mid);	if(r>mid) sum+=query(p[rot].r,l,r,mid+1,R);	return sum;}/*---------------dfs----------------*/inline void dfs(int u,int f){
   	in[u]=++sign;	pre[sign]=u;	for(int i=head[u];i!=-1;i=e[i].next)	{
   		int to=e[i].to;		if(to==f) continue;		dfs(to,u);	}	out[u]=sign;}int main(){
   	int x;	while(~scanf("%d",&n))	{
   		init();		map
    
     mp;		for(int i=2;i<=n;i++)		{
   			scanf("%d",&x);			add(x,i);			add(i,x);		}		for(int i=1;i<=n;i++) scanf("%d",&a[i]);		dfs(1,0);		for(int i=n+1;i<=n*2;i++) pre[i]=pre[i-n];		root[0]=build(1,maxx);		for(int i=1;i<=n*2;i++)		{
   			int u=pre[i];			if(mp[a[u]]==0) root[i]=update(root[i-1],1,maxx,i,1);			else			{
   				root[i]=update(root[i-1],1,maxx,mp[a[u]],-1);				root[i]=update(root[i],1,maxx,i,1);			}			mp[a[u]]=i;		}		int ans=0;		for(int i=1;i<=n;i++) 		{
   			int xx=query(root[out[i]],in[i],out[i],1,maxx);//以区间右端点的版本，从l~r区间的数字个数			int yy=query(root[in[i]+n-1],out[i]+1,in[i]+n-1,1,maxx);			ans=max(ans,xx+yy);		}		printf("%d\n",ans);	}	return 0;}
    
   

很巧妙的一道题，awsl

努力加油a啊，(^o)/~

转载地址：http://sktvi.baihongyu.com/