CF1092F Tree with Maximum Cost（dfs+dp)

果然我已经菜到被div3的题虐哭了

qwq

首先看到这个题，一个比较显然的想法就是先从1号点开始dfs一遍，然后通过一些奇怪的方式，再dfs一遍得到其他点的贡献。

那么具体应该这么做呢。
首先，我们维护两个数组dis[i]表示i到1的距离，sum[i]表示i的子树中的val的和。

然后我们考虑，如果从fa[x]移动到x，相当于x的子树内的dis都要减一，对ans的贡献是−sum[x]，然后x的子树外面的所有的点的dis要加一，对ans的贡献是sum[1]−sum[x]。

那么我们只需要两遍dfs，第二遍dfs，一边dfs一边更新ans就好。

#include<bits/stdc++.h>
#define mk make_pair
#define pb push_back
#define ll long long
#define int long long

using namespace std;

inline int read()
{
  int x=0,f=1;char ch=getchar();
  while (!isdigit(ch)) {if (ch==\'-\') f=-1;ch=getchar();}
  while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-\'0\';ch=getchar();}
  return x*f;
}

const int maxn = 4e5+1e2;
const int maxm = 2*maxn;

int point[maxn],nxt[maxm],to[maxm];
int dis[maxn],sum[maxn];
int ans;
int n,m,cnt;
int tmp;
int val[maxn];

void addedge(int x,int y)
{
    nxt[++cnt]=point[x];
    to[cnt]=y;
    point[x]=cnt;
} 

void dfs(int x,int fa,int dep)
{
    sum[x]=val[x];
    dis[x]=dep;
    for (int i=point[x];i;i=nxt[i])
    {
        int p = to[i];
        if(p==fa) continue;
        dfs(p,x,dep+1);
        sum[x]+=sum[p];
    }
}

void solve(int x,int fa,int now)
{
    ans=max(ans,now);
    for (int i=point[x];i;i=nxt[i])
    {
        int p=to[i];
        if (p==fa) continue;
        solve(p,x,now+sum[1]-sum[p]-sum[p]); 
    }
}

signed main()
{
  n=read();
  for (int i=1;i<=n;i++) val[i]=read();
  for (int i=1;i<n;i++)
  {
  	int x=read(),y=read();
  	addedge(x,y);
  	addedge(y,x);
  }
  dfs(1,0,0);
  for (int i=1;i<=n;i++) tmp=tmp+dis[i]*val[i];
  ans=tmp;
  //cout<<ans<<endl;
  solve(1,0,tmp); 
  cout<<ans;
  return 0;
}