$O(n)$

给定的是一个图,距离为2的只能是一直往下的两个点和一个点左右，我们可以遍历树的时候对这两种情况进行遍历即可.

#include<bits/stdc++.h>
using namespace std;
const int N=200010,M=N*2,MOD=10007;
int n;
int h[N],e[M],ne[M],idx;
int w[N];
int ans_max,ans_sum;
void add(int a,int b) //加边函数
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u,int fa)
{
    int pre_max=0,presum=0;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(j==fa) continue;//说明是往回搜的
        if(fa!=-1) //一条往下的
        {
            ans_max=max(ans_max,w[j]*w[fa]);
            ans_sum=(ans_sum+w[j]*w[fa])%MOD;
        }
        ans_max=max(ans_max,pre_max*w[j]); //左右的
        ans_sum=(ans_sum+presum*w[j])%MOD; //
        pre_max=max(pre_max,w[j]); //更新最大值
        presum=(presum+w[j])%MOD; //更新和
        dfs(j,u);//继续看后面的部分
    }
}
int main()
{
    cin>>n;
    memset(h,-1,sizeof h);
    for(int i=0;i<n-1;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    for(int i=1;i<=n;i++)
    {
        cin>>w[i];
    }
    dfs(1,-1);
    cout<<ans_max<<" "<<ans_sum*2%MOD;
    return 0;
}