洛谷P1351 [NOIP 2014 提高组] 联合权值
洛谷题目传送门
题目背景
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% 的数据, 1 < n ≤ 100 1 < n \leq 100 1<n≤100;
- 对于 60 % 60\% 60% 的数据, 1 < n ≤ 2000 1 < n \leq 2000 1<n≤2000;
- 对于 100 % 100\% 100% 的数据, 1 < n ≤ 2 × 1 0 5 1 < n \leq 2\times 10^5 1<n≤2×105, 0 < W i ≤ 10000 0 < W_i \leq 10000 0<Wi≤10000。
保证一定存在可产生联合权值的有序点对。
思路详解
虽然这个题目说他是一个图,但由n-1条边的连通图可得他是一棵树,思考如何求解出最大值与和。
最大值
首先考虑哪些点可以凑成一个联合点对???由于只要距离为2,那显然对于一个节点 u u u, u u u的任意子节点 v v v,都可以和 u u u的其余所有子节点组成联合点对,也可以和 u u u的父亲节点组成点对。那最大值就很显然了:
- v v v与其他子节点组合:显然我们只需要找出最大值 d 1 d_{1} d1与次大值 d 2 d_{2} d2组合即可。
- v v v与 u u u的父亲组合:直接找到最大值 d 1 d1 d1与 a f a u a_{fa_{u}} afau组合即可。
和
与上面相同,我们只需要分为两部分求解即可。具体如下:
- v v v与 u u u的父亲组合:令 u u u的所有子节点权值和为 s u m u sum_{u} sumu,则这一部分答案 a n s 2 = s u m u ∗ a f a u ans_{2}=sum_{u}*a_{fa_{u}} ans2=sumu∗afau。
- v v v与其他子节点组合:则这一部分的答案为 a n s 3 = ∑ v a v ∗ ( s u m u − a v ) ans_{3}=\sum _{v} a_{v}*(sum_{u}-a_{v}) ans3=∑vav∗(sumu−av)因为他不能与他自己组合。
但我们发现联合点对是有序的,那我们是否输出 2 ( a n s 2 + a n s 3 ) 2(ans_{2}+ans_{3}) 2(ans2+ans3)呢???虽然这样样例可以过,但我们只能得到0分的好成绩,这是为何?我们发现 a n s 3 ans_{3} ans3其实已经相当于乘过2了,只有 a n s 2 ans_{2} ans2需要乘2。这就是水样例的恶劣影响。
code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=5e5+5,mod=10007;
ll n,a[N];
ll h[N],to[N],ne[N],tot=0;
void add(ll u,ll v){//建边tot++;to[tot]=v;ne[tot]=h[u];h[u]=tot;
}
ll d1[N],d2[N],ans1=0,sum[N],ans2=0,ans3=0;
//d1[u]为u的子节点的最大值,d2[u]为次大值,sum[u]为u的子节点的和。
void dfs(ll u,ll fa){d1[u]=-0x3f3f3f3f;d2[u]=-0x3f3f3f3f;//赋初值sum[u]=0;for(ll i=h[u];i;i=ne[i]){ll v=to[i];if(v==fa)continue;sum[u]=(sum[u]+a[v])%mod;if(a[v]>d1[u]){d2[u]=d1[u];d1[u]=a[v];}//更新最大值else if(a[v]>d2[u]){d2[u]=a[v];}//更新次大值dfs(v,u);}for(ll i=h[u];i;i=ne[i]){//求解ans3ll v=to[i];if(v==fa)continue;ans3=(ans3+a[v]*((sum[u]-a[v]+mod)%mod)%mod)%mod;}ans2=(ans2+sum[u]*a[fa]%mod)%mod;//求解ans2if(d1[u]==-0x3f3f3f3f&&d2[u]==-0x3f3f3f3f)return;//没有子节点,不更新ans1ans1=max(ans1,max(d1[u]*d2[u],d1[u]*a[fa]));
}
int main(){cin>>n;for(ll i=1;i<=n-1;i++){ll x,y;cin>>x>>y;add(x,y);add(y,x);}for(ll i=1;i<=n;i++)cin>>a[i];sum[0]+=a[1];dfs(1,0);cout<<ans1<<' '<<(ans2*2+ans3)%mod;return 0;
}
/*高级样例
5
1 2
1 3
2 4
2 5
1 2 4 6 5
*/