还是先看题吧：
|
试题描述
|
|
无向连通图 G 有 n 个点，n-1 条边。点从 1 到 n 依次编号，编号为 i 的点的权值为 Wi ，每条边的长度均为 1。图上两点(u, v)的距离定义为 u 点到 v 点的最短距离。对于图 G 上的点对(u, v)，若它们的距离为 2，则它们之间会产生Wu * Wv 的联合权值。请问图 G 上所有可产生联合权值的有序点对中，联合权值最大的是多少？所有联合权值之和是多少？
|
|
输入
|
|
第一行包含 1 个整数 n。
接下来 n-1 行，每行包含 2 个用空格隔开的正整数 u、v，表示编号为 u 和编号为 v 的点之间有边相连。 最后 1 行，包含 n 个正整数，每两个正整数之间用一个空格隔开，其中第 i 个整数表示图 G 上编号为 i 的点的权值为 Wi。 |
|
输出
|
|
输出共 1 行，包含 2 个整数，之间用一个空格隔开，依次为图 G 上联合权值的最大值和所有联合权值之和。由 于 所 有 联 合 权 值 之 和 可 能 很 大 ， 输 出 它 时 要 对 10007 取 余 。
|
|
输入示例
|
|
5
1 2 2 3 3 4 4 5 1 5 2 3 10 |
|
输出示例
|
|
20 74
|
|
其他说明
|
|
样例说明：距离为 2 的有序点对有(1,3)、(2,4)、(3,1)、(3,5)、(4,2)、(5,3)。其联合权值分别为 2、15、2、20、15、20。其中最大的是 20，总和为 74。
数据范围：对于 100% 的数据，1 < n ≤ 200,000，0 < Wi ≤ 10,000。 |
十分郁闷，只过了7个点，剩下3个点莫名其妙在第二个数值上WA了。
还是先说思路吧，首先看到n的范围，肯定就是用邻接表存了（注意无向图要正着反着各存一次），还有题目中所说无相连通图有n个节点,n-1条边，说明这是一棵树。然后就开始求解了，第一问：可以依次枚举，但是这样太慢了。我们可以针对每一个节点，通过邻接表来找到它的所有邻居，然后依次判断他们的点权，对于每一个节点维护两个值，该点邻居中点权的第一大和第二大，扫过一遍之后，我们只需找哪一个点第一大与第二大乘积最大即可求出第一问。下面是第二问：看到第二问大家第一反应肯定是找到该点的所有邻居，然后每两个点一次算一遍点权的乘积，累加起来就是结果，第二反应就是这样是O（n^2）的复杂度，不用想肯定超时，第三反应就是设法想到O(N)或O（N log N）的算法。然后就开始想：对于一个节点p，他的邻居a,b,c,d,e……我们需要算ab+ac+ad+……bc+bd……这样能不能用数学公式来实现呢？由于最近刷学校留的暑假作业（初高中数学衔接读本），里面正好有一个章节就在讲因式分解，其中公式背的很6：(a+b)^2=a^2+b^2+2ab,(a+b+c)^2=a^2+b^2+c^2+2*(ab+ac+bc)……然后就立刻联想到其中的ab+ac+bc不就正是我要求的吗？知道这样，我们针对每一个点，只需把这个点的邻居的平方和以及和的平方维护即可，到时候一相减即可算出，时间复杂度O(N)。
下面是代码：
#include<iostream>
#include<queue>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<conio.h>
using namespace std;
const int maxn=+;
int n,u[maxn],v[maxn],w[maxn],first[*maxn],next[*maxn],a,b,MAX,lMAX,ans1,sum1,sum2,ans2;
int read()
{
int f=,x=;
char ch=getchar();
if(ch=='-') f=-;
while(ch<''||ch>'')
{
if(ch=='-')f=-;
ch=getchar();
}
while(ch>=''&& ch<='') { x=x*+ch-''; ch=getchar(); }
return x*f;
}
void addEdge(int i,int a,int b)//加边
{
u[i]=a;v[i]=b;
next[i]=first[a];
first[a]=i;
}
int main()
{
memset(first,-,sizeof(first));
n=read();
for(int i=;i<n-;i++)
{
a=read();b=read();
addEdge(*i,a,b);
addEdge(*i+,b,a);
}
for(int i=;i<=n;i++)w[i]=read();
for(int i=;i<=n;i++)
{
sum1=sum2=MAX=;
lMAX=-;
for(int j=first[i];j!=-;j=next[j])
{
if(w[v[j]]>lMAX)//维护最大值和次最大值
{
if(w[v[j]]>MAX)MAX=w[v[j]];
else lMAX=w[v[j]];
}
sum1=(sum1+w[v[j]])%;//维护邻居中点权的和
sum2=(sum2+(w[v[j]]%*w[v[j]]%)%)%;//维护邻居中点权的平方和
}
ans1=max(ans1,MAX*lMAX);
ans2=(ans2+(((sum1*sum1)%-sum2))+)%; //套公式
}
printf("%d %d",ans1,ans2);
return ;
}
其中还有一个注意事项，就是代码55行中加了一个10007,因为这些都是取模运算，并且其中还有相减的运算，所以很有可能算成负数，因此我们需要加上一个10007这样就能解决出负数的问题了（其实钱老师在讲食物链的时候提到过），以后一定要牢记这些经验教训。