30pts

使用floyd预处理出来每两个点的距离，然后进行更新。

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int d[N][N];
int w[N];
int main()
{
	int n;
	cin>>n;
	memset(d,0x3f,sizeof d);
	for(int i=1;i<=n;i++) d[i][i]=0;
	for(int i=1;i<n;i++)
	{
		int a,b;
		cin>>a>>b;
		d[a][b]=1;
		d[b][a]=1;
	}
	for(int i=1;i<=n;i++)
	{
		cin>>w[i];
	}
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
			}
		}
	}
	int maxv=0,sum=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(d[i][j]==2)
			{
				maxv=max(maxv,w[i]*w[j]);
				sum+=w[i]*w[j]%10007;
			}
		}
	}
	cout<<maxv<<" "<<sum%10007;
	return 0;
}

70pts

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

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
const int MOD=10007;
vector<int> g[N];
int w[N];
int ans_max,ans_sum;
void dfs(int u,int fa)
{
	vector<int> v=g[u];
    for(int i=0;i<v.size();i++)
    {
    	int j=v[i];
        if(j==fa) continue;
        if(fa!=-1) //说明存在j往上走的距离为2的点
        {
            ans_max=max(ans_max,w[j]*w[fa]);
            ans_sum=(ans_sum+w[j]*w[fa])%MOD;
        }
        //左右的点计算
       	for(int k=i+1;k<v.size();k++)
		{
		   	ans_max=max(ans_max,w[j]*w[v[k]]);
            ans_sum=(ans_sum+w[j]*w[v[k]])%MOD;
		} 
        dfs(j,u);//继续往下搜索
    }
}
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n-1;i++)
    {
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for(int i=1;i<=n;i++)
    {
        cin>>w[i];
    }
    dfs(1,-1);
    cout<<ans_max<<" "<<ans_sum*2%MOD;
    return 0;
}

100pts

在枚举左右点的时候，我们可以使用前缀最大值和前缀和进行优化

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
const int MOD=10007;
vector<int> g[N];
int w[N];
int ans_max,ans_sum;
void dfs(int u,int fa)
{
    int pre_max=0,pre_sum=0;
    for(auto j:g[u])
    {
        if(j==fa) continue;
        if(fa!=-1) //说明存在j往上走的距离为2的点
        {
            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+w[j]*pre_sum)%MOD;
        pre_max=max(pre_max,w[j]);
        pre_sum=(pre_sum+w[j])%MOD;
        dfs(j,u);//继续往下搜索
    }
}
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n-1;i++)
    {
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for(int i=1;i<=n;i++)
    {
        cin>>w[i];
    }
    dfs(1,-1);
    cout<<ans_max<<" "<<ans_sum*2%MOD;
    return 0;
}