CF F - Tree with Maximum Cost (树形DP)给出你一颗带点权的树，dist(i, j)的值为节点i到j的距离乘上节点j的权值，让你任意找一个节点v，使得dist(v, i) (1 < i < n)的和最大。输出最大的值。

题目意思：

给出你一颗带点权的树，dist(i, j)的值为节点i到j的距离乘上节点j的权值，让你任意找一个节点v，使得dist(v, i) (1 < i < n)的和最大。输出最大的值。

题目分析：

首先如果你可以熟悉的使用树形dp的话 ， 可以很快的意识的先从1号点开始dfs一遍，然后通过一些奇怪的方式，再dfs一遍得到其他点的贡献。无所以我们需要找到一个递推式是满足我选择其他号码为根时候，可以很快的得到答案 。 现在假设有两个节点v , fa ; v 是 fa 的儿子节点 , 根据dp的性质 与dfs的遍历顺序， 如果已经的遍历到 dp[v] 了 ， 那dp[fa] 就一定是最优的答案 ， 那显然 有式子 dp[v] = dp[fa]-sum[v]  + sum[1]-sum[v] ;

为什么这样呢？  这个很好想 ， 如果v是根的话 ，  sum[1]-sum[v] 就是计算的是（不是v子树）的贡献 ， dp[fa]-sum[v] ， 应为对dp[fa] 来说 结果已经是有sum[v] 的值了 ， 这就是多的部分 ；

以上是自己的奇思妙想；

这篇博客解释的很好呀，大牛来的

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn =  * 1e5 + ;

ll dp[maxn], sum[maxn], head[maxn];

int n, top;

ll ans;

struct node {                      //链式前向星存树，可以更换为其他的存储方式

    int v, next;

}edge[maxn * ];

inline void add (int u, int v)     //建边

{

    edge[top].v = v;

    edge[top].next = head[u];

    head[u] = top++;

}

void dfs(int u , int fa) //求出根为1的时候的dp

{

    for(int i=head[u] ; i!=- ; i=edge[i].next)

    {

        int v=edge[i].v;

        if(v!=fa)

        {

            dfs(v,u);

            sum[u]+=sum[v];

            dp[u] +=sum[v]+dp[v];

        }

    }

}

void solve(int u , int fa)

{

    if(u!=)

    dp[u]=dp[fa]-sum[u]+sum[]-sum[u];

    for(int i=head[u] ; i!=- ; i=edge[i].next)

    {

        int v=edge[i].v;

        if(v!=fa)

        solve(v,u);

    }

    ans=max(ans,dp[u]);

}

int main()

{

    int n;

    scanf("%d",&n);

    memset(head,-,sizeof(head));

    memset(dp,,sizeof(dp));

    for(int i= ; i<=n ; i++)

    {

        scanf("%I64d",&sum[i]);

    }

    int u,v;

    for(int i= ; i<=n- ; i++)

    {

        scanf("%d%d",&u,&v);

        add(u,v);

        add(v,u);

    }

    dfs(,);

    solve(,);

    printf("%I64d\n",ans);

}

CF F - Tree with Maximum Cost (树形DP)给出你一颗带点权的树，dist(i, j)的值为节点i到j的距离乘上节点j的权值，让你任意找一个节点v，使得dist(v, i) (1 < i < n)的和最大。输出最大的值。的相关教程结束。