#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define LL long long
using namespace std;
template <class _T> inline void read(_T &_x){
int _t;bool _flag=0;
while((_t=getchar())!='-'&&(_t>'9'||_t<'0'));
if(_t=='-')_flag=1,_t=getchar();_x=_t-'0';
while((_t=getchar())>='0'&&_t<='9')_x=_x*10+_t-'0';
if(_flag)_x=-_x;
}
const int maxn=2e5+5;
const int MOD=10007;
int n,x,y,head[maxn],du[maxn],cnt;
LL w[maxn],ans1,ans2;
struct edge{
int v,nxt;
}d[maxn<<1];
inline void add(int a,int b){
d[++cnt].v=b;d[cnt].nxt=head[a];head[a]=cnt;
d[++cnt].v=a;d[cnt].nxt=head[b];head[b]=cnt;
}

int main(){
read(n);
for(int i=1;i<n;++i){
read(x),read(y);
add(x,y);du[x]++;du[y]++;
}
for(int i=1;i<=n;++i){
read(w[i]);
}
for(int i=1;i<=n;++i){
if(du[i]<=1)continue;
LL s1=0,s2=0,w1=0,w2=0;
for(int k=head[i];k;k=d[k].nxt){
int v=d[k].v;
if(w1<w[v])w2=w1,w1=w[v];
else if(w2<w[v])w2=w[v];
s1+=w[v];s2+=w[v]*w[v];
s1%=MOD;s2%=MOD;
}
ans1=max(ans1,w1*w2);
ans2+=(s1*s1%MOD-s2+MOD)%MOD;ans2%=MOD;
}
printf("%lld %lld",ans1,ans2);

return 0;
}

0 条评论

目前还没有评论...

信息

ID
1405
难度
9
分类
图结构 点击显示
标签
递交数
4
已通过
4
通过率
100%
上传者