洛谷 P1351 联合权值 —— 树形DP

时间：2024-10-09 08:06:25

题目：https://www.luogu.org/problemnew/show/P1351

树形DP，别忘了子树之间的情况(拐一下距离为2)。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

int const maxn=2e5+,mod=;

int n,hd[maxn],ct,to[maxn<<],nxt[maxn<<];

ll w[maxn],ans,sum,mxx[maxn],s[maxn];

int rd()

{

  int ret=,f=; char ch=getchar();

  while(ch<''||ch>''){if(ch=='-')f=-; ch=getchar();}

  while(ch>=''&&ch<='')ret=(ret<<)+(ret<<)+ch-'',ch=getchar();

  return ret*f;

}

void add(int x,int y){to[++ct]=y; nxt[ct]=hd[x]; hd[x]=ct;}

void dfs(int x,int f)

{

  ll ns=,nm=;//不是全局变量！

  for(int i=hd[x],u;i;i=nxt[i])

    {

      if((u=to[i])==f)continue;

      dfs(u,x); sum=(sum+s[u]*w[x])%mod;

      ans=max(ans,mxx[u]*w[x]);

      s[x]+=w[u]; mxx[x]=max(mxx[x],w[u]);

      sum=(sum+ns*w[u])%mod; ns+=w[u];

      ans=max(ans,nm*w[u]); nm=max(nm,w[u]);

    }

}

int main()

{

  n=rd();

  for(int i=,x,y;i<n;i++)

    {

      x=rd(); y=rd();

      add(x,y); add(y,x);

    }

  for(int i=;i<=n;i++)w[i]=rd();

  dfs(,);

  printf("%lld %lld\n",ans,(sum*)%mod);

  return ;

}

相关文章