#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int MAX_N=200000+16;
const int INF=0x30303030;//尽可能的大
const int MOD=10007;

vector<int> G[MAX_N];
int V;
int maxn=-1;
int ans;
int val[MAX_N];
int main()
{
cin >>V;
for(int i=1;i<=V-1;i++)
{
int from,to;
cin >>from >>to;
G[from].push_back(to);
G[to].push_back(from);
}
for(int i=1;i<=V;i++)
cin>>val[i];

for(int i=1;i<=V;i++)
{
int sum=0;
int max_1=0;
int max_2=0;
for(int j=0;j<G[i].size();j++)
{
int v=G[i][j];
ans+=2*sum*val[v];
ans%=MOD;
sum+=val[v];
if(val[v]>max_1)
{

max_2=max_1;
max_1=val[v];
}
else if(val[v]>max_2)
max_2=val[v];
}
if(max_1*max_2>maxn)
maxn=max_1*max_2;
}

cout<<maxn<<' '<<ans<<endl;

return 0;
}
为什么TME呢，求大神指点

蒟蒻来一发（￣▽￣）~

这个题目的关键就是整个无向图其实就是一棵树
那么和同一个父亲节点相连的子节点之间的距离必定是2
然后每个编号的节点都可以看作父亲节点，子节点就可以用邻接表存储了，不必担心爆内存

然后找最大联合权值其实就是找一个父亲节点连的所有子节点里面最大和第二大的权值然后就能产生最大联合权值
总联合权值=∑每个父亲节点的总联合权值
而每个父亲节点的总联合权值=W1*0+W1*W2+(W1+W2)*W3+(W1+W2+W3)*W4+...+(W1+...+Wn-1)*Wn
这样在遍历所有子节点的时候，可以一边找最大和第二大的权值，一边逐层求和算总权值，边加边取余以防爆int
W_total+=((∑W1+...Wn-1)%10007)*Wn*2%10007
这样需要遍历每个父亲节点，并遍历接下来的子节点，由于边数=节点数-1，所以应该比较快的

###Inline Code
#include<cstdio>
int n,path[400001][2],index[200001],w[200001];

int main()
{
int i,j,a,b,k,sum,max_1,max_2,max_t=0,w_t=0;
freopen("link10.in","r",stdin);

scanf("%d",&n);
for(i=1;i<n*2-1;i+=2)
{
scanf("%d%d",&a,&b); //以邻接表读入无向图 (用数组实现啦）

path[i][0]=b;
path[i][1]=index[a];
index[a]=i;

path[i+1][0]=a;
path[i+1][1]=index[b];
index[b]=i+1;
}

for(i=1;i<=n;i++) scanf("%d",&w[i]); //读入每个点的权值

for(i=1;i<=n;i++) //开始遍历每个父亲节点
{
a=index[i]; //初始化
sum=0; //子节点权值累加
max_1=0; //子节点中最大的权值
max_2=0; //子节点中第二大的权值

while(path[a][0]) //遍历与每个父亲节点相连的所有子节点
{

b=w[path[a][0]]; //读取当前子节点的权值

if(b>max_1) max_1 = b; //搜索子节点最大和第二大的权值
else max_2 = max_2>b ? max_2:b;

w_t+=(sum%10007)*b*2%10007; //Sum乘以当前子节点权值再乘2并取余10007
w_t%=10007;

sum+=b; //对之前遍历的子节点权值进行累加求和

a=path[a][1]; //跳转到下一个子节点
}

k=max_1*max_2; //得到当前父亲节点的最大联合权值并比较全局最大联合权值
max_t=max_t>k ? max_t:k;
}

printf("%d %d",max_t,w_t); //输出结果
return 0;
}

Block code

测试数据 #0: Accepted, time = 0 ms, mem = 4936 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 4936 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 4936 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 4940 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 4936 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 4940 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 4940 KiB, score = 10
测试数据 #7: Accepted, time = 62 ms, mem = 4936 KiB, score = 10
测试数据 #8: Accepted, time = 109 ms, mem = 4940 KiB, score = 10
测试数据 #9: Accepted, time = 109 ms, mem = 4940 KiB, score = 10

Accepted, time = 295 ms, mem = 4940 KiB, score = 100

#include<stdio.h>
#include<stdlib.h>
const int maxn=200010,mod=10007;
struct edge{
int x,next;

};
int w[maxn],s[maxn],last[maxn],max1[maxn],max2[maxn];
struct edge e[maxn*3];
int ans,maxans,k;
void add(int u,int v){
e[++k].x=v;
e[last[u]].next=k;

last[u]=k;

}
int main(){
int i,j,m,n,u,v;
scanf("%d",&n);
k=n;
for(i=1;i<=n;i++){ e[i].x=i; last[i]=i; }
for(i=1;i<n;i++){
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
for(i=1;i<=n;i++)scanf("%d",&w[i]);
for(i=1;i<=n;i++)
for(j=e[i].next; j ;j=e[j].next){
m=w[e[j].x];
s[i]=(s[i]+m)%mod;
if(m>max1[i]){
max2[i]=max1[i];
max1[i]=m;

}else if(m>max2[i])
max2[i]=m;
}
for(int i=1;i<=n;i++)
maxans=maxans>max1[i]*max2[i]?maxans:max1[i]*max2[i];
for(i=1;i<=n;i++)
for(j=e[i].next; j ;j=e[j].next){
m=e[j].x;
ans=(ans+w[i]*(s[m]-w[i])%mod+mod)%mod;

}

printf("%d %d\n",maxans,ans);

return 0;
}
优化邻接表
(非原创，只是推广下)

测试数据 #0: Accepted, time = 0 ms, mem = 6292 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 6292 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 6296 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 6296 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 6292 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 6292 KiB, score = 10
测试数据 #6: Accepted, time = 31 ms, mem = 6292 KiB, score = 10
测试数据 #7: Accepted, time = 93 ms, mem = 6296 KiB, score = 10
测试数据 #8: Accepted, time = 171 ms, mem = 6292 KiB, score = 10
测试数据 #9: Accepted, time = 140 ms, mem = 6296 KiB, score = 10
Accepted, time = 450 ms, mem = 6296 KiB, score = 100

program link;
var n,i,total,max:longint;
a,b,w,c,ans,max1,max2:array[1..200005]of longint;
begin
fillchar(a,sizeof(a),0);
fillchar(w,sizeof(w),0);
fillchar(c,sizeof(c),0);
fillchar(b,sizeof(b),0);
fillchar(ans,sizeof(ans),0);
fillchar(max1,sizeof(max1),0);
fillchar(max2,sizeof(max2),0);
readln(n);
for i:=1 to n-1 do
readln(a[i],b[i]);
for i:=1 to n do
begin
read(c[i]);
c[i]:=c[i] mod 10007;
end;
for i:=1 to n-1 do
begin
ans[a[i]]:=(ans[a[i]]+2*c[b[i]]*w[a[i]] mod 10007)mod 10007;
ans[b[i]]:=(ans[b[i]]+2*c[a[i]]*w[b[i]] mod 10007)mod 10007;
inc(w[a[i]],c[b[i]]);
inc(w[b[i]],c[a[i]]);
w[a[i]]:=w[a[i]] mod 10007;
w[b[i]]:=w[b[i]] mod 10007;
if c[b[i]]>max1[a[i]] then
begin
max2[a[i]]:=max1[a[i]];
max1[a[i]]:=c[b[i]];
end
else if c[b[i]]>max2[a[i]] then max2[a[i]]:=c[b[i]];
if c[a[i]]>max1[b[i]] then
begin
max2[b[i]]:=max1[b[i]];
max1[b[i]]:=c[a[i]];
end
else if c[a[i]]>max2[b[i]] then max2[b[i]]:=c[a[i]];
end;
total:=0;
for i:=1 to n do
begin
total:=(total+ans[i]) mod 10007;
if max1[i]*max2[i]>max then max:=max1[i]*max2[i];
end;
writeln(max,' ',total);
end.

首先，由于无向联通图 G 有 n 个点，n-1 条边，因此 G 中必定无环，即若存在边 (a,b) 和 (b,c)，则一定不存在边 (a,c)。
因此，设边集合为 E，所求联合权值最大值为 M，联合权值之和为 S，一个基本的\(O(n^2)\)算法为
$$
M = \max_{(u,w)\in E}\max_{(w,v)\in E, v\neq u} W_u W_v
$$$$
S = \sum_{(u,w)\in E}\sum_{(w,v)\in E, v\neq u} W_u W_v
$$
可以通过提前计算
$$
M_w = \max_{(w,v)\in E} W_v
$$$$
M_w' = \max_{(w,v)\in E, v\neq u, W_u = M_w} W_v
$$$$
S_w = \sum_{(w,v)\in E} W_v
$$
从而得到\(O(n)\)的算法
$$
M = \max_{(u, w)\in E}
\left\{ \begin{array}{lr}
W_u M_w & W_u \neq M_w \\
W_u M_w' & W_u = M_w
\end{array} \right.
$$$$
S = \sum_{(u, w)\in E} W_u (S_w - W_u)
$$

沙发.

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct Edge{ int v,nt; } G[400010];
int h[200010],n,cnt=0,s[200010],qm=0; long long ans=0ll;
void adj(int a,int b){
    G[++cnt]=(Edge){b,h[a]}; h[a]=cnt;
    G[++cnt]=(Edge){a,h[b]}; h[b]=cnt; 
}
int main(){
    scanf("%d",&n);
    for(int x,y,i=1;i++<n;adj(x,y)) scanf("%d%d",&x,&y);
    for(int i=1;i<=n;++i) scanf("%d",s+i);
    for(int i=1;i<=n;++i){
        int sv=0,zm=0,zq=0;
        for(int v,j=h[i];j;j=G[j].nt){
            if(s[v=G[j].v]>zm){ zq=zm; zm=s[v]; }
            else if(s[v]>zq) zq=s[v];
            ans+=sv*s[v]; sv=(sv+s[v])%10007;
        }
        qm=max(qm,zm*zq);
    }
    printf("%d %d\n",qm,(ans<<1)%10007);
}

看到题解各种大牛，我看不懂，还是自己写一份吧lalala
本来打算存图，邻接矩阵不用说肯定会爆炸，然后又在那里搞邻接表，搞不来.....那我也没办法了
只好看看其他的方法喽。
看到n个点与n-1条边，以为发现了树，很好，但是并没有什么用
那就不管了，不存啦
首先是用一个二维数组map来读入，map是记录边的，然后map[1,i]是记录这条边左边的点，同理map[2,i]记录的是这条边右边的点
再用数组wealth来记录点的权值。
对于最大的联合权值，我们不难想到，只要找到这个点的相邻的最大权值和第二大权值，并且更新就可以得到最大联合权值
然后来考虑权值之和。
假如A与B,C相连，wealth分别为b,c;那么所有的联合权值为bc+cb=2bc;
同理对于A与B,C,D相连，wealth为b,c,d；画下图，那么answer=bc+bd+cb+cd+db+dc=2bc+2bd+2cd；对于2bc我们可以想到完全平方公式(a+b)^2=a^2+2ab+b^2得2ab=(a+b)^2-(a^2+b^2);那么同理2bc+2bd+2cd=(b+c+d)^2-(b^2+c^2+d^2)并以此类推即只要枚举所有的点的联合权值之和，并加起来便可以得到最后答案
弱渣一只，图论shangwei入门
附上代码：
```pascal
program p1906;
const maxn=200001;
mode=10007;
var map:array [1..2,1..maxn] of int64;
i:longint;
n,x,y,ans,l,r,total:int64;
max1,max2,wealth:array[1..maxn] of int64;
add,multiply:array[1..maxn] of int64;

function max(x,y:int64):int64;
begin
if x>=y then exit(x)
else exit(y);
end;

procedure domax;
begin
for i:=1 to n-1 do
begin
l:=map[1,i];
r:=map[2,i];
add[l]:=(add[l]+wealth[r]) mod mode;
add[r]:=(add[r]+wealth[l]) mod mode;
multiply[l]:=(multiply[l]+wealth[r]*wealth[r]) mod mode;
multiply[r]:=(multiply[r]+wealth[l]*wealth[l]) mod mode;
if wealth[l] > max1[r] then
begin
max2[r]:=max1[r];
max1[r]:=wealth[l];
end
else if wealth[l] > max2[r] then
max2[r]:=wealth[l];
if wealth[r] > max1[l] then
begin
max2[l]:=max1[l];
max1[l]:=wealth[r];
end
else if wealth[r] > max2[l] then
max2[l]:=wealth[r];
end;
for i:=1 to n do
ans:=max(ans,max1[i]*max2[i]);
end;

procedure doit;
begin
total:=0;
for i:=1 to n do
total:=(total+(sqr(add[i])-multiply[i]) mod mode) mod mode;
end;

begin
readln(n);
ans:=0;
fillchar(max1,sizeof(max1),0);
fillchar(max2,sizeof(max2),0);
fillchar(add,sizeof(add),0);
fillchar(multiply,sizeof(multiply),0);
for i:=1 to n-1 do
begin
read(x,y);
map[1,i]:=x;
map[2,i]:=y;
end;
for i:=1 to n do
read(wealth[i]);
domax;
doit;
writeln(ans,' ',total);

end.
```

** 粗体
* 斜体

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cctype>
using namespace std;
const int M = 200005;
const int MOD = 10007;

int read(){
int x = 0; char c = getchar();
while(!isdigit(c)) c = getchar();
while(isdigit(c)) x = x*10 + c - '0', c = getchar();
return x;
}

int n, w[M], cnt = 0;
struct Edge{
int to;
Edge *r;
}map[M], bri[M*2];

void add(int a, int b){
bri[++cnt].to = b;
bri[cnt].r = map[a].r;
map[a].r = &bri[cnt];
}

void solve(){
int ans1 = 0, ans2 = 0;
for(int x = 1; x <= n; x++){
int tot = 0, max1 = 0, max2 = 0;
for(Edge *i = map[x].r; i != NULL; i = i->r){
int e = i->to;
ans1 = (ans1 + w[e] * tot) % MOD;
tot = (tot + w[e]) % MOD;
if(w[e] > max1) max2 = max1, max1 = w[e];
else if(w[e] > max2) max2 = w[e];

}
ans2 = max(ans2, max1 * max2);
}
printf("%d %d\n", ans2, (ans1 * 2) % MOD);
}

int main()
{
n = read();
for(int i = 1; i <= n; i++) map[i].r = NULL;
for(int i = 1; i < n; i++){
int u = read(), v = read();
add(u, v);
add(v, u);
}
for(int i = 1; i <= n; i++) scanf("%d", &w[i]);
solve();
return 0;
}

C++ 26行AC代码
c++
#include <bits/stdc++.h>
using namespace std;
int n,w[200005],amax,maxn[200005][2];vector<pair<int,int> > input;
long long cnt[200005],acnt;
int main()
{
ios::sync_with_stdio(0);
cin>>n;
for(int i=1;i<n;i++){int j,k;cin>>j>>k;input.push_back(make_pair(j,k));}
for(int i=1;i<=n;i++)cin>>w[i];
for(vector<pair<int,int> >::iterator i=input.begin();i!=input.end();i++)
{
int j=i->first,k=i->second;
cnt[j]+=w[k],cnt[k]+=w[j];
if(w[k]>maxn[j][0])maxn[j][1]=maxn[j][0],maxn[j][0]=w[k];else if(w[k]>maxn[j][1])maxn[j][1]=w[k];
if(w[j]>maxn[k][0])maxn[k][1]=maxn[k][0],maxn[k][0]=w[j];else if(w[j]>maxn[k][1])maxn[k][1]=w[j];
}
for(int i=1;i<=n;i++)amax=max(amax,maxn[i][0]*maxn[i][1]);
for(vector<pair<int,int> >::iterator i=input.begin();i!=input.end();i++)
{
int j=i->first,k=i->second;
acnt=(acnt+(w[j]*(cnt[k]-w[j]))%10007+(w[k]*(cnt[j]-w[k]))%10007)%10007;
}
cout<<amax<<' '<<acnt;
return 0;
}