[HDU6504]Split The Tree

又学会了一个知识点。

题目大意:
给你一个有$n$个节点的树,每个节点有一个权值$w[i]$,一棵树的价值为树上所有不同的权值的数量。现在你可以删除一条边,问删除一条边后两棵树的价值之和最大为多少。

点击查看原题面

Split The Tree

You are given a tree with n vertices, numbered from 1 to n. i-th vertex has a value $w_i$.
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 tree weights.
We want to know the maximal score we can get if we delete the edge optimally.

Input
Input is given frome Standard Input in the following format:
$n$
$p_2$ $p_3$ … $p_n$
$w_1$ $w_2$ … $w_n$
Constraints
$2\leq n \leq 100000$ ,$1\leq p_i < i$ , $1 \leq w_i 100000(1\leq i\leq n)$ , and they are integers.
$p_i$ means there is a edge between $p_i$ 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$序即为每个点的在一次$DFS$中的遍历顺序,从定义可以知道,子树上的每个节点的$DFS$序一定连续,因此我们可以求出每棵子树所对应的区间,剩下的节点即为另一棵树。

此时我们就可以利用树状数组求每个区间里面不同的数的个数,由于一个子树区间可能会在数组中间,会将剩下的数字分为左右两部分,因此我们需要将原权值数组扩充一倍,然后进行计算。

需要注意的是,现在这个权值数组不是输入的权值数组,而是根据$DFS$序进行重新排序的数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include<bits/stdc++.h>
using namespace std;

const int maxn=100000+10;

struct node{
int l,r,id;
int ans;
}q[maxn*2];
struct point{//pos为DFS序,size为子树大小,即对应的DFS序区间长度
int w,pos,size;
}a[maxn*2];

vector<int>vec[maxn];
int w[maxn],vis[maxn],sum[maxn*2];
int n,x,tot;

bool cmp1(node i,node j){
if(i.r==j.r) return i.l<j.l;
return i.r<j.r;
}
bool cmp2(node i,node j){
return i.id<j.id;
}
bool cmp3(point i,point j){
return i.pos<j.pos;
}

int lowbit(int x){return x&(-x);};
void change(int x,int p){
while(x<=n*2){
sum[x]+=p;
x+=lowbit(x);
}
}
int getsum(int x){
int ans=0;
while(x){
ans+=sum[x];
x-=lowbit(x);
}
return ans;
}
void dfs(int x){
a[x].pos=++tot;
a[x].size=1;
for(int i=0;i<vec[x].size();i++){
int y=vec[x][i];
dfs(y);
a[x].size+=a[y].size;
}
}
void init(){
tot=0;
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++){
vec[i].clear();
sum[i*2]=sum[i*2-1]=0;
}
}
void solve(){
init();
for(int i=2;i<=n;i++){
scanf("%d",&x);
vec[x].push_back(i);
}
for(int i=1;i<=n;i++){
scanf("%d",&a[i].w);
}
dfs(1);
sort(a+1,a+n+1,cmp3);//按照DFS序进行排序
for(int i=1;i<=n;i++) a[i+n]=a[i];

for(int i=2;i<=n;i++){//创建n*2个区间,每两个区间互补
q[i*2].l=a[i].pos;
q[i*2].r=a[i].pos+a[i].size-1;
q[i*2].id=i*2;
q[i*2-1].l=q[i*2].r+1;
q[i*2-1].r=q[i*2].l+n-1;
q[i*2-1].id=i*2-1;
}
//以下为树状数组离线求区间不同数的个数
sort(q+3,q+n*2+1,cmp1);
int num=3;
for(int i=1;i<=n*2 && num<=n*2;i++){
if(vis[a[i].w]) change(vis[a[i].w],-1);
change(i,1);
vis[a[i].w]=i;
while(q[num].r==i && num<=n*2){
q[num].ans=getsum(q[num].r)-getsum(q[num].l-1);
num++;
}
}
sort(q+3,q+n*2+1,cmp2);
int ans=0;
for(int i=2;i<=n;i++){//两棵树的总和
ans=max(ans,q[i*2].ans+q[i*2-1].ans);
}
printf("%d\n",ans);
}
int main()
{
// freopen("1.in","r",stdin);
while(~scanf("%d",&n))
solve();
return 0;
}
感谢您的支持
-------------本文结束感谢您的阅读-------------