联合权值题解
程序员文章站
2022-05-22 14:35:08
...
题目
无向连通图 GG 有 个点,条边。点从 到 依次编号,编号为 的点的权值为 ,每条边的长度均为 。图上两点 的距离定义为 uu 点到 vv 点的最短距离。对于图 上的点对 ,若它们的距离为 ,则它们之间会产生* 的联合权值。请问图 上所有可产生联合权值的有序点对中,联合权值最大的是多少?所有联合权值之和是多少?
输入输出格式
输入格式:
第一行包含 个整数 。
接下来 行,每行包含 个用空格隔开的正整数,表示编号为 和编号为 的点之间有边相连。最后 1 行,包含 n 个正整数,每两个正整数之间用一个空格隔开,其中第 i个整数表示图 上编号为 i 的点的权值为
输出格式:
输出共 1行,包含2 个整数,之间用一个空格隔开,依次为图 G 上联合权值的最大值和所有联合权值之和。由于所有联合权值之和可能很大,输出它时要对10007取余。
输入输出样例
输入样例#1:
5
1 2
2 3
3 4
4 5
1 5 2 3 10
输出样例#1:
20 74
分析
我们来看,因为边权是1,所以我们可枚举点从而进行计算,但这样只有70分,这样我们就要来想一想如何优化,我们分析可发现我们将大部分时间都浪费在找点,所以我们可维护一个数组,表示有多少个点与之相连,这样在枚举点时可以减少一重循环,这样就可以A了
上代码
#include<bits/stdc++.h>
using namespace std;
struct Edge
{
int t,nexty;
Edge(){t=nexty=0;}
}edge[1000000];
int head[300000]={0},cnt=0;
void add(int a,int b){
cnt++;
edge[cnt].t=b,edge[cnt].nexty=head[a];
head[a]=cnt;
}
long long w[300000]={0};
int main(){
int n;
scanf("%d",&n);
int a,b;
for(int i=0;i<n-1;i++){
scanf("%d%d",&a,&b);
add(a,b),add(b,a);
}
for(int i=1;i<=n;i++)scanf("%lld",&w[i]);
long long sum=0,maxn=0,he,rmax,node;
for(int i=1;i<=n;i++){
node=head[i];
he=(rmax=w[edge[node].t])%10007;
node=edge[node].nexty;
for(;node!=0;node=edge[node].nexty){
sum=(sum+he*w[edge[node].t])%10007;
maxn=max(maxn,rmax*w[edge[node].t]);
he=(he+w[edge[node].t])%10007;
rmax=max(rmax,w[edge[node].t]);
}
}
printf("%lld %lld",maxn,(sum*2)%10007);
return 0;
}