题解 P1351 【联合权值】

· · 题解

终于过了这一题。（实际上只有一次提交……）

此题其实还是挺巧妙的。思路我想了半天才想出来，要是在考场直接打的话，未必能够打的出来。

首先，此题说的比较的隐晦。所谓的有n-1条边，n个点的无相连通图，其实就是一颗无根树。换句话说，没有一个环。所以，要是两个点同于另一个点相连，则它们不可能再有边相连，即它们之间的距离为2.

于是，思路就隐隐出来了：枚举每一个点，取其任意两个点，然后进行组合，然后两两相乘，得到最大值与他们的和。将所有值统计一下，然后注意因为和是组合出来的，所以再乘2，输出就可以了。

这里先申明一个坑点：题目只说了对和取模，没有说对最大值取模，所以要注意，如果对最大值取模就错了。

然后就是对于每一个点的问题了。如果直接组合，则n^2复杂度会TLE。我们可以使用乘法结合律和前缀和的思想。对于一个点，因为用邻接表存储，所以线性扫过所有与他相连的点，然后动态更新目前的和与目前这些点中的最大值，然后再到下一个点时，将下一个点的权值与这两个值相乘，然后做相应的处理就行了。类似于DP。

再注意一下细节，此题便做完了。

代码如下（不到50行，超简洁~）：

#include<cstdio>
#include<cmath>
using namespace std;
struct Edge
{
    int t,nexty;
    Edge(){t=nexty=0;}
}edge[1000000];//链式前向星邻接表
int head[300000]={0},cnt=0;//链式前向星链表变量
void add(int a,int b)//加边
{
    cnt++;
    edge[cnt].t=b,edge[cnt].nexty=head[a];
    head[a]=cnt;//加边过程（如果不懂链式前向星，可以百度一下）
}
long long w[300000]={0};//每个点的权值
int main()
{
    int n;
    scanf("%d",&n);
    int a,b;
    for(int i=0;i<n-1;i++)
    {
        scanf("%d%d",&a,&b);
        add(a,b),add(b,a);//加边
    }
    for(int i=1;i<=n;i++)scanf("%lld",&w[i]);//读入权值
    long long sum=0,maxn=0;//全局的和，最大值
    long long he,rmax;//一段的和与一段的最大值
    int node;
    for(int i=1;i<=n;i++)
    {
        node=head[i];//第一个元素
        he=(rmax=w[edge[node].t])%10007;//得到初始值
        node=edge[node].nexty;//下一个
        for(;node!=0;node=edge[node].nexty)//枚举与之相连的点
        {
            sum=(sum+he*w[edge[node].t])%10007;//乘法结合律
            maxn=max(maxn,rmax*w[edge[node].t]);//贪心，取最大值
            he=(he+w[edge[node].t])%10007;
            rmax=max(rmax,w[edge[node].t]);//更新
        }
    }
    printf("%lld %lld",maxn,(sum*2)%10007);//记得*2
    return 0;
}