P1351 联合权值
网页链接
P1351 联合权值 
题目背景
NOIP2014 提高组 D1T2
题目描述
无向连通图
G
G
G 有
n
n
n 个点，
n
−
1
n-1
n−1 条边。点从
1
1
1 到
n
n
n 依次编号,编号为
i
i
i 的点的权值为
W
i
W_i
Wi，每条边的长度均为
1
1
1。图上两点
(
u
,
v
)
(u, v)
(u,v) 的距离定义为
u
u
u 点到
v
v
v 点的最短距离。对于图
G
G
G 上的点对
(
u
,
v
)
(u, v)
(u,v)，若它们的距离为
2
2
2，则它们之间会产生
W
v
×
W
u
W_v \\times W_u
Wv×Wu 的联合权值。
请问图
G
G
G 上所有可产生联合权值的有序点对中，联合权值最大的是多少？所有联合权值之和是多少？
输入格式
第一行包含
1
1
1 个整数
n
n
n。
接下来
n
−
1
n-1
n−1 行,每行包含
2
2
2 个用空格隔开的正整数
u
,
v
u,v
u,v，表示编号为
u
u
u 和编号为
v
v
v 的点之间有边相连。
最后
1
1
1 行，包含
n
n
n 个正整数，每两个正整数之间用一个空格隔开，其中第
i
i
i 个整数表示图
G
G
G 上编号为
i
i
i 的点的权值为
W
i
W_i
Wi。
输出格式
输出共
1
1
1 行，包含
2
2
2 个整数，之间用一个空格隔开,依次为图
G
G
G 上联合权值的最大值和所有联合权值之和。由于所有联合权值之和可能很大，输出它时要对
10007
10007
10007 取余。
输入输出样例 #1
输入 #1
5
1 2
2 3
3 4
4 5
1 5 2 3 10
输出 #1
20 74
说明/提示
样例解释
本例输入的图如上所示，距离为
2
2
2 的有序点对有
(
1
,
3
)
(1,3)
(1,3) 、
(
2
,
4
)
(2,4)
(2,4) 、
(
3
,
1
)
(3,1)
(3,1) 、$(3,5)
、
、
、(4,2)$ 、$(5,3) $。
其联合权值分别为
2
,
15
,
2
,
20
,
15
,
20
2,15,2,20,15,20
2,15,2,20,15,20。其中最大的是
20
20
20，总和为
74
74
74。
数据说明
- 对于
30
%
30\\%
30% 的数据，2
<
n
≤
100
2 < n \\leq 100
2<n≤100； - 对于
60
%
60\\%
60% 的数据，2
<
n
≤
2000
2 < n \\leq 2000
2<n≤2000； - 对于
100
%
100\\%
100% 的数据，2
<
n
≤
2
×
10
5
2 < n \\leq 2\\times 10^5
2<n≤2×105，0
<
W
i
≤
10000
0 < W_i \\leq 10000
0<Wi≤10000。
保证一定存在可产生联合权值的有序点对。
解题思路
本题是树上距离为2的点对统计问题，核心思路是枚举中间节点 + 数学公式优化，将复杂度从暴力的平方级降至线性，适配十万级数据规模。
树中任意距离为2的点对，必然存在且仅存在一个公共邻接点（中间节点）。因此我们可以枚举每个节点作为中间点，统计其所有邻接点两两之间产生的联合权值，分别累加总和与更新最大值：
u
u
u，设其邻接点权值为
w
1
,
w
2
,
…
,
w
k
w_1,w_2,\\dots,w_k
w1,w2,…,wk。所有有序点对的乘积和可由平方和公式推导：
∑
i
≠
j
w
i
w
j
=
(
∑
i
=
1
k
w
i
)
2
−
∑
i
=
1
k
w
i
2
\\sum_{i \\neq j} w_i w_j = \\left(\\sum_{i=1}^k w_i\\right)^2 – \\sum_{i=1}^k w_i^2
i=j∑wiwj=(i=1∑kwi)2−i=1∑kwi2 只需遍历一次邻接点，维护权值和与平方和，即可在
O
(
k
)
O(k)
O(k) 时间内算出该节点贡献的总权值，无需两两枚举。
u
u
u，邻接点中权值最大的两个数的乘积，就是以
u
u
u 为中间点的最大联合权值。遍历邻接点时维护最大值与次大值，相乘后更新全局最大值即可。
最终遍历所有节点后，全局最大值即为答案的第一部分，所有节点贡献的权值和取模后即为答案的第二部分。算法总时间复杂度为
O
(
n
)
O(n)
O(n)，因为树的总边数为
n
−
1
n-1
n−1，所有节点的度数之和为
2
(
n
−
1
)
2(n-1)
2(n−1)，遍历无冗余。
总结
核心逻辑：将距离为2的点对转化为共享中间节点的邻接点对，通过数学公式与最值维护线性求解总和与最大值。 关键操作：链式前向星存树、平方和公式计算总权值、维护最大次大权值更新全局最大值、全程取模处理总和。 效率保障：仅一次遍历所有节点与边，无嵌套循环，线性复杂度完美适配二十万节点的数据规模。
代码简要说明
代码内容
#include <bits/stdc++.h>
using namespace std;
#define endl '\\n'
typedef long long ll;
typedef unsigned long long ull;
typedef vector<vector<ll>> vvt;
typedef pair<ll,ll> pll;
const ll N=1e3+10;
const ll INF=1e18;
const ll M=1e6+10;
const ll mod=1e9+7;
struct edge
{
ll next;
ll to;
}a[400005];
ll edgenum,head[200005],w[200005];
ll n,ans,maxx;
void add(ll u,ll v)
{
a[++edgenum].next=head[u];
a[edgenum].to=v;
head[u]=edgenum;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
scanf("%lld",&n);
for(ll i=1;i<n;i++)
{
ll u,v;
scanf("%lld%lld",&u,&v);
add(u,v);
add(v,u);
}
for(ll i=1;i<=n;i++) scanf("%lld",&w[i]);
for(ll i=1;i<=n;i++)
{
ll max1=0,max2=0;
ll t1=0,t2=0;
for(ll j=head[i];j;j=a[j].next)
{
if(w[a[j].to]>max1){max2=max1; max1=w[a[j].to];}
else if(w[a[j].to]>max2) max2=w[a[j].to];
t1=(t1+w[a[j].to])%10007;
t2=(t2+w[a[j].to]*w[a[j].to])%10007;
}
t1=t1*t1%10007;
ans=(ans+t1+10007–t2)%10007;
if(maxx<max1*max2) maxx=max1*max2;
}
printf("%lld %lld\\n",maxx,ans);
return 0;
}
