本题练习用邻接表储存图，之后对每个点的邻接点统计最大值，次大值，总和
联合权值即为每组中最大值×次大值的最大一个。每个组的总和为累加和的平方-每个点的值平方，每次操作均取模，防止爆long long
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
int n;
struct node
{int v;int next;
} a[400005];
int head[200005], w[200005] = { 0 };
int cnt = 0,maxnum = 0;
long long sum = 0;
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 u, int v)//邻接表
{a[++cnt].v = v;a[cnt].next = head[u];head[u] = cnt;
}int calc(int m)
{int biggist = 0, second = 0;int nodesum = 0, nodetocut = 0;int n = head[m];while (n != 0){int wn = w[a[n].v];nodesum += wn;nodetocut += wn*wn;nodetocut %= 10007;if (biggist <= wn){second = biggist;biggist = wn; }else if (second <= wn){second = wn;}n = a[n].next;}sum += (nodesum % 10007)* (nodesum % 10007) - nodetocut;sum %= 10007;return biggist * second;
}int main()
{int u, v;n = read();for (int i = 1; i < n; ++i){u = read();v = read();add(u, v);add(v, u);}for (int i = 1; i <= n; ++i){w[i] = read();}for (int i = 1; i <= n; ++i){maxnum = max(maxnum, calc(i));}cout << maxnum << " " << sum;return 0;
}