[Split The Tree][dfs序+树状数组求区间数的种数]

Split The Tree

时间限制: 1 Sec 内存限制: 128 MB
提交: 46 解决: 11
[提交] [状态] [讨论版] [命题人:admin]

题目描述

You are given a tree with n vertices, numbered from 1 to n. ith vertex has a value wi
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 is given from Standard Input in the following format:
n
p2 p3 . . . pn
w1 w2 . . . wn
Constraints
2 ≤ n ≤ 100000 ,1 ≤ pi < i
1 ≤ wi ≤ 100000(1 ≤ i ≤ n), and they are integers
pi means there is a edge between pi and i

输出

Print one number denotes the maximal score.

样例输入

3
1 1
1 2 2

样例输出

3
题意：给一棵树，每个节点都有权值，删除一条边会变成两棵树，每棵树的价值是树上不同权值的个数，求max(两棵树的价值和)
题解：dfs序可以将树上的问题转化为易于操作的线性区间问题(子树是dfs序中连续的区间)。这题通过dfs序转化为求区间数字的种数，通过树状数组求解。注意求区间数的种数的方法：通过vector存储区间左端点，从总区间的起始点开始往后遍历，不断update树状数组中当前点代表权值的位置(即把当前点权值的上一个位置的值-1,把当前位置+1)，并且用树状数组计算以当前点为终点的区间种数和

  1 #include<iostream>
  2 #include<cstring>
  3 #include<algorithm>
  4 #include<cmath>
  5 #include<cstdio>
  6 #include<vector>
  7 #include<queue>
  8 using namespace std;
  9 typedef long long ll;
 10 struct edge{
 11     int x;
 12     int y;
 13     int nex;
 14 }e[200005];
 15 struct pot{
 16     int pre;
 17     int id;
 18 };
 19 vector<struct pot>g[200005];
 20 int n,cnt,tot,head[100005],q[100005],w[200005],c[200005],dfn[100005],r[100005],vis[100005],ans[200005];
 21 void adde(int x1,int y1){
 22     e[cnt].x=x1;
 23     e[cnt].y=y1;
 24     e[cnt].nex=head[x1];
 25     head[x1]=cnt++;
 26 }
 27 int lowbit(int x){
 28     return x&(-x);
 29 }
 30 void update(int x,int y,int n){
 31     for(int i=x;i<=n;i+=lowbit(i))
 32         c[i] += y;
 33 }
 34 int query(int x){
 35     int ak=0;
 36     for(int i=x;i>0;i-=lowbit(i)){
 37         ak+=c[i];
 38     }
 39     return ak;
 40 }
 41 void dfs(int u,int fa){
 42     w[++tot]=u;
 43     w[tot+n]=u;
 44     dfn[u]=tot;
 45     for(int i=head[u];i!=-1;i=e[i].nex){
 46         int v=e[i].y;
 47         if(v==fa)continue;
 48         if(dfn[v])continue;
 49         dfs(v,u);
 50     }
 51     r[u]=tot;
 52 }
 53 int main(){
 54     scanf("%d",&n);
 55     memset(head,-1,sizeof(head));
 56     for(int i=2;i<=n;i++){
 57         int a;
 58         scanf("%d",&a);
 59         adde(a,i);
 60         adde(i,a);
 61     }
 62     for(int i=1;i<=n;i++){
 63         scanf("%d",&q[i]);
 64     }
 65     dfs(1,-1);
 66     for(int i=0;i<cnt;i+=2){
 67         int u=e[i].x;
 68         int v=e[i].y;
 69         int L=dfn[u];
 70         int R=r[u];
 71         int L1=dfn[v];
 72         int R1=r[v];
 73         struct pot aaa,bbb;
 74         if(R!=n){
 75             aaa.id=i;
 76             aaa.pre=L;
 77             bbb.id=i;
 78             bbb.pre=R+1;
 79             g[R].push_back(aaa);
 80             g[L-1+n].push_back(bbb);
 81         }
 82         else{
 83             aaa.id=i;
 84             aaa.pre=L1;
 85             bbb.id=i;
 86             bbb.pre=R1+1;
 87             g[R1].push_back(aaa);
 88             g[L1-1+n].push_back(bbb);
 89         }
 90     }
 91     for(int i=1;i<=n*2;i++){
 92         if(vis[q[w[i]]]){
 93             update(vis[q[w[i]]],-1,n*2);
 94         }
 95         vis[q[w[i]]]=i;
 96         update(vis[q[w[i]]],1,n*2);
 97         for(int j=0;j<g[i].size();j++){
 98             struct pot ccc=g[i][j];
 99             ans[ccc.id]+=query(i)-query(ccc.pre-1);
100         }
101     }
102     int ans0=0;
103     for(int i=0;i<cnt;i+=2){
104         ans0=max(ans0,ans[i]);
105     }
106     cout<<ans0<<endl;
107     return 0;
108 }

View Code