首页 > itarticle > codeforces 1092f. tree with maximum cost

codeforces 1092f. tree with maximum cost

admin 11月 23, 2020 0

Overview

题出得好！难度适中！覆盖知识点广！又比较切合实际背景，解法也比较自然！给出题人点赞！

题意

题目链接
定义以$rt$为根的树的一种统计方式为$f_{rt} = sumlimits_{u=1wedge unot= rt}^{n}dist_{rt, u}cdot a_u$，问$max{f_{rt} | 1leq rtleq n}$.

题解

最暴力的做法就是按照题意枚举根来统计，然后$f_{rt}$的计算是可以在一次dfs内完成的，时间复杂度是$O(n^2)$.
考虑优化，不难发现如果我们已经知道了$f_u$，那么对于$u$的孩子结点$v$，我们也能很快地计算出答案：$f_v = f_u - a_v + a_1 - a_v$，表示把$v$“splay”到根，然后前一部分是$u$除去$v$以后的贡献，后一部分是树上除去$v$的贡献，其中$a$是点权的树上前缀和。


#define N 200100
using namespace std;

inline char () {
    static char buf[1000000], *p1 = buf, *p2 = buf;
    return ((p1 == p2) && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2)) ? EOF : *p1++;
}

template <typename Int> inline void read(Int& x) {
    x = 0; char ch = getc();
    for (; !(ch >= '0' && ch <= '9'); ch = getc());
    for (; ch >= '0' && ch <= '9'; x = x * 10 + ch - '0', ch = getc());
}

template <typename Int> inline void writeln(Int x) {
    if (x == 0) { puts("0"); return; }
    int digits = 0; char digit[110];
    for (; x; x /= 10) digit[++digits] = x % 10 + '0';
    for (int i = digits; i; --i) putchar(digit[i]);
    putchar('n');
}

struct Edge {
    int to, nxt;
    Edge() {}
    Edge(const int& to, const int& nxt) : to(to), nxt(nxt) {}
} e[N << 1];
int tot = 1, head[N];

inline void AddEdge(const int& u, const int& v) {
    e[tot] = Edge(v, head[u]), head[u] = tot++;
    e[tot] = Edge(u, head[v]), head[v] = tot++;
}

int n;
long long a[N], f[N];

inline void dfs1(int u, int fa, int d) {
    f[1] += 1LL * d * a[u];
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (v == fa) continue;
        dfs1(v, u, d + 1);
        a[u] += a[v];
    }
}

inline void dfs2(int u, int fa) {
    if (u > 1) f[u] = f[fa] + a[1] - 2 * a[u];
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (v == fa) continue;
        dfs2(v, u);
    }
}

int main() {
    
    read(n);
    for (int i = 1; i <= n; ++i) read(a[i]);
    for (int i = 1, u, v; i < n; ++i) {
        read(u), read(v);
        AddEdge(u, v);
    }
    dfs1(1, 0, 0);
    dfs2(1, 0);
    long long ret = 0;
    for (int i = 1; i <= n; ++i) ret = max(ret, f[i]);
    writeln(ret);
    return 0;
}