NOIP 2004 联合权值

时间:2022-06-20 19:12:46

洛谷 P1351 联合权值

洛谷传送门

JDOJ 2886: [NOIP2014]联合权值 D1 T2

JDOJ传送门

Description

无向连通图 G有 n个点,n-1条边。点从 1到 n依次编号,编号为 i的点的权值为 Wi,每条边的长度均为 1。图上两点 (u, v)的距离定义为 u点到 v点的最短距离。对于图 G上的点对(u, v),若它们的距离为 2,则它们之间会产生Wu×Wv的联合权值。

请问图 G上所有可产生联合权值的有序点对中,联合权值最大的是多少?所有联合权值之和是多少?

Input

第一行包含 1个整数 n。

接下来 n-1行,每行包含 2个用空格隔开的正整数 u、v,表示编号为 u和编号为 v的点之间有边相连。

最后 1行,包含 n个正整数,每两个正整数之间用一个空格隔开,其中第 i个整数表示图 G上编号为 i的点的权值为 Wi。

Output

输出共 1行,包含 2个整数,之间用一个空格隔开,依次为图 G上联合权值的最大值和所有联合权值之和。由于所有联合权值之和可能很大,输出它时要对 10007取余。

Sample Input

5 1 2 2 3 3 4 4 5 1 5 2 3 10

Sample Output

20 74

HINT

【样例说明】

本例输入的图如上所示,距离为 2的有序点对有(1,3)、(2,4)、(3,1)、(3,5)、(4,2)、(5,3)。其联合权值分别为 2、15、2、20、15、20。其中最大的是 20,总和为 74。

NOIP 2004 联合权值

【数据说明】

对于 30%的数据,1< n ≤100;

对于 60%的数据,1< n ≤2000;

对于 100%的数据,1< n ≤200,000,0< Wi ≤10,000。

标签给的LCA,纯属P话。

这题不需要LCA的过程。根据题面,这是一棵树。

保证了没有环。

然后呢?我们就能发现,距离为2的点会有联合权值,那么我们就可以断定,这两个点是连在一个父亲节点上的。

然后我们就可以得出枚举的大致思路。

先枚举每个点,枚举它的所有出边,记录最大值和次大值,这个最大值和次大值之积就是第一问的解。

比较麻烦的是第二问。

它需要累加联合权值,这个temp是每次枚举到一个节点的时候的中转值,它需要累加权值,最后的temp就是这个父亲节点所能拼凑出的所有联合权值的值,然后累加ans2,注意取模。

最后还有答案的特殊处理。

就这样AC吧

#include<cstdio>
#include<algorithm>
using namespace std;
const int mod=1e4+7;
int n,ans1,ans2;
int tot,to[400001],nxt[400001],head[200001],w[200001];
void add(int x,int y)
{
to[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
for(int i=1;i<=n;i++)
scanf("%d",&w[i]);
for(int i=1;i<=n;i++)
{
int max1=0,max2=0;
int temp=0;
for(int j=head[i];j;j=nxt[j])
{
int y=to[j];
if(w[y]>max1)
{
max2=max1;
max1=w[y];
}
else if(w[y]>max2)
max2=w[y];
ans2=(ans2+temp*w[y])%mod;
temp=(temp+w[y])%mod;
}
ans1=max(ans1,max1*max2);
}
printf("%d %d",ans1,(ans2*2)%mod);
return 0;
}