联合权值（link）

洛谷p1351
NOIP2014 day1 T2

题目概述

无向连通图 G 有 n 个点，n-1 条边。点从 1 到 n 依次编号，编号为 i 的点的权值为 w[i] ，每条边的长度均为 1。图上两点(u, v)的距离定义为 u 点到 v 点的最短距离。对于图 G 上的点对(u, v)，若它们的距离为 2，则它们之间会产生w[u]*w[v]的联合权值。请问图 G 上所有可产生联合权值的有序点对中，联合权值最大的是多少？所有联合权值之和是多少？

题解

由于此题只需要把距离为2的边统计出来，因此可以把每一类距离为2的边分类讨论。显然，这道题是一棵树。可以看出，这种边只有两种，一种是祖先-父亲-儿子（以下称祖孙边），另一种是同一个父亲的兄弟边。对于祖孙边，很好处理，对于要处理的点，把每个孙子点列出来，祖孙边的权值就知道了。对于兄弟边，只要把当前处理的点的每一个儿子都遍历一遍，经过父亲和其它儿子点就自然而然是一条兄弟边。如果要每一个儿子点和其它每一个儿子点都做一遍，时间复杂度太高了，所以可以用前缀和。至于最大权值，可以把最大的两个点记录下来，它们的联合权值肯定是这些兄弟边中最大的。
看程序吧：

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
int n,w[200005],ans,s,b[200005];//s表示联合权值和，ans表示最大联合权值 
vector<int> a[200005];
void dfs(int x)
{
    b[x]=1;//已做过就标记掉 
    int t1=0,t2=0,t=0;//t表示前缀和，t1表示儿子点中的最大权值，t2表示次大权值 
    for (int i=0;i<a[x].size();i++)//遍历儿子点 
    {
        if (b[a[x][i]]!=0) continue;//因为是无向图，避免做到父亲点 
        if (w[a[x][i]]>t1)//记录最大值和次大值 
        {
            t2=t1;
            t1=w[a[x][i]];
        }
        else if (w[a[x][i]]>t2) t2=w[a[x][i]];
        s=(s+w[a[x][i]]*t%10007)%10007;//处理兄弟边 
        t+=w[a[x][i]];//维护前缀和 
        t%=10007;//如果不做这一步会超过INT_MAX，然后就错了 
        for (int j=0;j<a[a[x][i]].size();j++)//处理祖孙边 
        {
            int y=a[a[x][i]][j];
            if (b[y]!=0) continue;
            s=(s+w[x]*w[y]%10007)%10007;
            ans=max(ans,w[x]*w[y]);
        }
    }
    ans=max(ans,t1*t2);
    for (int i=0;i<a[x].size();i++) if (b[a[x][i]]==0) dfs(a[x][i]);
}
int main()
{
    cin>>n;
    int x,y;
    for (int i=1;i<n;i++)
    {
        scanf("%d %d",&x,&y);
        a[x].push_back(y);//邻接表存边，无向边，所以要做两次 
        a[y].push_back(x);
    }
    for (int i=1;i<=n;i++) scanf("%d",&w[i]);
    dfs(1);//假设1号点为树根 
    cout<<ans<<' '<<s*2%10007;//前面都是单向做的，所以答案要乘以2 
}

总结

这道题虽然不是很难，但我初测只有40分。我以为每一步都mod 10007，最后就不用了，测了样例之后才想到要乘以2，可忘记还要mod 10007。改了之后还是只有70分，原来是前缀和在计算的时候没有mod 10007，这样就超过了INT_MAX，前缀和就变成了负数。这次题目没做好，原因还是细节没有处理好。以后遇到mod的题目可一定要小心，每一步都要注意mod。