CF1092F Tree with Maximum Cost

Link

题意描述：

• 有一棵 (n) 个节点的树，每个点有一个权值 (a_i)。

• 定义 (operatorname{dist}(u,v)) 为 (u,v) 两点间距离。

• 您要找到一个点 (u)，使得 (displaystylesum_{i=1}^noperatorname{dist}(i,u)cdot a_i)

  最大。您只需求出最大值。

• (1le n,a_ile 2 imes 10^5)。

---

换根dp水题

按照套路先按题意模拟出 以 (1) 为根的答案，然后考虑怎么换根。

我们设 (sum) 表示所有点的点权和， (f[x]) 表示 (x) 的子树中所有点的点权和。

(g[x]) 表示以 (x) 为根的答案。

当我们以 (x) 为根的时候，相比于 以 (fa[x]) 为根的时候， (x) 子树中的点到 (x) 的距离减少 (1) , (x) 的子树外的点到 (x) 的距离增加1

所以答案的变化量就是 (sum-2 imes f[x])

换根的公式也就很好写出来了， (g[x] = g[fa[x]] + sum - 2 imes f[x])

不开 long long 见祖宗

然后这道题就做完了。

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define int long long
const int N = 2e5+10;
int n,tot,sum,u,v,ans;
int head[N],g[N],a[N],f[N];
struct node
{
    int to,net;
}e[N<<1];
inline int read()
{
    int s = 0,w = 1; char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0'; ch = getchar();}
    return s * w;
}
void add(int x,int y)
{
    e[++tot].to = y;
    e[tot].net = head[x];
    head[x] = tot;
}
void dfs(int x,int fa,int dep)//先求出以1为根的答案，以及 f 数组
{
    g[1] += a[x] * dep; f[x] = a[x];
    for(int i = head[x]; i; i = e[i].net)
    {
        int to = e[i].to;
        if(to == fa) continue;
        dfs(to,x,dep+1);
        f[x] += f[to];
    }
}
void dp(int x,int fa)//换根
{
    for(int i = head[x]; i; i = e[i].net)
    {
        int to = e[i].to;
        if(to == fa) continue;
        g[to] = g[x] + sum - 2 * f[to];
        dp(to,x);
    }
}
signed main()
{
    n = read();
    for(int i = 1; i <= n; i++)
    {
        a[i] = read();
        sum += a[i];
    }
    for(int i = 1; i <= n-1; i++)
    {
        u = read(); v = read();
        add(u,v); add(v,u);
    }
    dfs(1,1,0); dp(1,1);
    for(int i = 1; i <= n; i++)
    {
        ans = max(ans,g[i]);
    }
    printf("%lld
",ans);
    return 0;
}