首页 > 其他 > 详细

Split The Tree

时间:2019-08-30 11:14:45      阅读:79      评论:0      收藏:0      [点我收藏+]

Problem E. Split The Tree

Time Limit: 7000/4000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 409    Accepted Submission(s): 109


Problem Description
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
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
 

 

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
 

 

Source
 
#include <bits/stdc++.h>

using namespace std;
const int maxn = 6e5 + 10;
int n;
int val[maxn], dfn[maxn], l[maxn], r[maxn], tot, cnt, nx[maxn], to[maxn], c[maxn], vis[maxn];
vector<int> G[maxn];

struct node {
    int L, R, pos;

    bool operator<(const node &cur) const {
        if (L == cur.L)return R < cur.R;
        return L < cur.L;
    }

} o[maxn];

inline void dfs(int cur, int f) {
    l[cur] = ++tot;
    dfn[tot] = val[cur];
    for (register int i = 0; i < G[cur].size(); ++i) {
        int to = G[cur][i];
        if (to == f)continue;
        dfs(to, cur);
    }
    r[cur] = tot;
}

inline int lowbit(int x) {
    return x & (-x);
}

inline void update(int pos, int val) {
    while (pos <= n) {
        c[pos] += val;
        pos += lowbit(pos);
    }
}

inline int query(int pos) {
    int res = 0;
    while (pos) {
        res += c[pos];
        pos -= lowbit(pos);
    }
    return res;
}

int q[maxn];

int main() {
#ifndef ONLINE_JUDGE
    freopen("1.txt", "r", stdin);
#endif
    while (scanf("%d", &n) != EOF) {
        tot = 0;
        memset(q, 0, sizeof(q));
        for (register int i = 1; i <= n; ++i) {
            G[i].clear();
        }
        for (register int i = 2, pi; i <= n; ++i) {
            scanf("%d", &pi);
            G[pi].emplace_back(i);
            G[i].emplace_back(pi);
        }
        int mx = -1;
        for (register int i = 1; i <= n; ++i) {
            scanf("%d", &val[i]);
            mx = max(mx, val[i]);
        }
        dfs(1, -1);
        cnt = 0;
        for (register int i = 0; i <= mx; ++i) {
            to[i] = 2 * n + 1;
            vis[i] = 0;
        }
        for (register int i = 1; i <= n; ++i) {
            dfn[i + n] = dfn[i];
            o[++cnt] = node{l[i], r[i], i};
            o[++cnt] = node{r[i] + 1, l[i] - 1 + n, i};
        }
        sort(o + 1, o + 1 + cnt);
        n *= 2;

        for (register int i = n; i >= 1; --i) {
            nx[i] = to[dfn[i]];
            to[dfn[i]] = i;
            c[i] = 0;
        }
        for (register int i = 1; i <= n; ++i) {
            if (!vis[dfn[i]]) {
                vis[dfn[i]] = 1;
                update(i, 1);
            }
        }
        int Left = 1, res = 0;
        for (register int i = 1; i <= cnt; ++i) {
            while (Left < o[i].L) {
                if (nx[Left] <= n)update(nx[Left], 1);
                ++Left;
            }
            q[o[i].pos] += query(o[i].R) - query(o[i].L - 1);
            res = max(res, q[o[i].pos]);
        }
        printf("%d\n", res);
    }
    return 0;
}

 

Split The Tree

原文:https://www.cnblogs.com/czy-power/p/11433485.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!