[NOIP2014 提高组] 联合权值
题目描述
无向连通图 \(G\) 有 \(n\) 个点，\(n-1\) 条边。点从 \(1\) 到 \(n\) 依次编号,编号为 \(i\) 的点的权值为 \(W_i\)，每条边的长度均为 \(1\)。图上两点 \((u, v)\) 的距离定义为 \(u\) 点到 \(v\) 点的最短距离。对于图 \(G\) 上的点对 \((u, v)\)，若它们的距离为 \(2\)，则它们之间会产生 \(W_v \times W_u\) 的联合权值。
请问图 \(G\) 上所有可产生联合权值的有序点对中，联合权值最大的是多少？所有联合权值之和是多少？
输入格式
第一行包含 \(1\) 个整数 \(n\)。
接下来 \(n-1\) 行,每行包含 \(2\) 个用空格隔开的正整数 \(u,v\)，表示编号为 \(u\) 和编号为 \(v\) 的点之间有边相连。
最后 \(1\) 行，包含 \(n\) 个正整数，每两个正整数之间用一个空格隔开，其中第 \(i\) 个整数表示图 \(G\) 上编号为 \(i\) 的点的权值为 \(W_i\)。
输出格式
输出共 \(1\) 行，包含 \(2\) 个整数，之间用一个空格隔开,依次为图 \(G\) 上联合权值的最大值和所有联合权值之和。由于所有联合权值之和可能很大，输出它时要对 \(10007\) 取余。
样例 #1
样例输入 #1
5
1 2
2 3
3 4
4 5
1 5 2 3 10
样例输出 #1
20 74
提示
样例解释
本例输入的图如上所示，距离为 \(2\) 的有序点对有\((1,3)\) 、\((2,4)\) 、\((3,1)\) 、$(3,5) \(、\)(4,2)$ 、$(5,3) $。
其联合权值分别为 \(2,15,2,20,15,20\)。其中最大的是 \(20\)，总和为 \(74\)。
数据说明
- 对于 \(30\%\) 的数据，\(1 < n \leq 100\)；
- 对于 \(60\%\) 的数据，\(1 < n \leq 2000\)；
- 对于 \(100\%\) 的数据，\(1 < n \leq 2\times 10^5\)，\(0 < W_i \leq 10000\)。
保证一定存在可产生联合权值的有序点对。
analysis:
这道题连dfs都不需要，只需要建立起边。第一问比较简单，对于每一个点，它的所有儿子节点中最大和次大相乘，打擂台即可。
第二问，求所有的联合权值，暴力需要n2。需要数学方式转换一下。比如一个节点的儿子是a1,a2,a3，我们希望得到(a1*a2+a1*a3+a2*a3)*2，可以发现这个结果等同于(a1+a2+a3)2-a12-a2-a^3，因此可以求出每个节点所有儿子节点的和的平方，以及平方和。注意，需要用到long long.
#include<bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;
int n, hd[200005], ans, cnt, x, y, a[200005];
long long res;
struct Edge{
int to, nxt;
}edge[400005];
void add(int u, int v){
edge[++cnt].to = v;
edge[cnt].nxt = hd[u];
hd[u] = cnt;
}
signed main(){
cin>>n;
for(int i = 1; i <= n-1; i++){
cin>>x>>y;
add(x,y); add(y,x);
}
for(int i = 1; i <= n; i++) cin>>a[i];
for(int u = 1; u <= n; u++){
int mx1 = 0, mx2 = 0, sum1 = 0, sum2 = 0;
for(int i = hd[u]; i; i = edge[i].nxt){
int v = edge[i].to;
if(a[v] > mx1) mx2 = mx1, mx1 = a[v];//这个地方没有更新mx2
else if(a[v] > mx2) mx2 = a[v];
sum1 += a[v]%10007;
sum2 += 1ll*a[v]*a[v]%10007;
}
ans = max(ans, mx1*mx2);//没有%10007,T-T
res = ((res + 1ll*sum1*sum1 % 10007 - sum2) % 10007 + 10007) % 10007;
}
cout<<ans<<" "<<res<<endl;
return 0;
}