联合权值

弱鸡也来写题解混牛币了~
虽然太菜了只好写写暴力的水题..

题解

题目说，n个点n-1条边的无向连通图..这不就是树嘛..
那见到树就喜欢去想dfs..求所有的有序点对，但是权值是无序的，所以只需把每个联合权值算两次即可
考虑到距离为2的两点在树形结构中仅有两种，一是当前点的儿子节点与当前点的父亲节点，二是两个当前点的儿子节点。
首先考虑儿子节点和父亲节点，在dfs过程中进行遍历更新最大联合权值，并将所有权值叠加累计最终答案到即可。
其次是两个儿子节点，对于每个儿子节点，都需要与其兄弟节点相乘并乘2，也就是与所有兄弟节点的和相乘并乘2，为了减小复杂度，可以记录所有兄弟节点的权值和，计算时用当前节点权值乘其他兄弟节点减去所有当前节点权值即可，由于每两个兄弟节点之间都算了两次，所以刚好满足有序点对计算两次的条件。

代码

#include <bits/stdc++.h>
#define reg register
#define ll long long
#define ull unsigned long long
#define pii pair<ll,ll>
#define inf 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
#define e exp(1.0)
#define ios ios::sync_with_stdio(false)
#define rep(i,l,r) for(ll i=(l);i<(r);i++)
using namespace std;

const ll maxn = 2e5 + 10;
const ll mod = 1e4 + 7;

vector<ll> son[maxn];
ll val[maxn];
ll res = 0;    //联合权值之和
ll mx = 0;    //最大联合权值

void dfs(ll x,ll fa)
{
   ll sum = 0;   //兄弟节点和
   vector<ll> s; //兄弟节点
   ll now = 0;   //兄弟节点中最大值
   for(ll i = 0;i < son[x].size();++i){
      ll to = son[x][i];
      if(to == fa) continue;
      dfs(to,x);
      sum = (sum + val[to]) % mod;
      s.push_back(val[to]);
      if(fa != 0) {
         res = (res + 2 * val[to] * val[fa] % mod) % mod;
         mx = max(mx,val[to] * val[fa]);
      }
      mx = max(now * val[to],mx);
      now = max(now,val[to]);
   }
   for(ll i = 0;i < s.size();++i){
      res = (res  +  ((sum - s[i] + mod) % mod * s[i]) % mod ) % mod;
   }
}

int main()
{
   ll n;
   cin>>n;
   for(ll i = 1;i <= n-1;++i){
      ll u,v;
      cin>>u>>v;
      son[u].push_back(v);
      son[v].push_back(u);
   }
   for(ll i = 1;i <= n;++i){
      cin>>val[i];
   }
   dfs(1,0);
   printf("%lld %lld\n",mx,res);

   return 0;
}