无向连通图G 有n 个点,n - 1 条边。点从1 到n 依次编号,编号为 i 的点的权值为W i ,每条边的长度均为1 。图上两点( u , v ) 的距离定义为u 点到v 点的最短距离。对于图G 上的点对( u, v) ,若它们的距离为2 ,则它们之间会产生Wu
×Wv 的联合权值。
请问图G 上所有可产生联合权值的有序点对中,联合权值最大的是多少?所有联合权值之和是多少?
输入输出格式输入格式:输入文件名为link .in。
第一行包含1 个整数n 。
接下来n - 1 行,每行包含 2 个用空格隔开的正整数u 、v ,表示编号为 u 和编号为v 的点之间有边相连。
最后1 行,包含 n 个正整数,每两个正整数之间用一个空格隔开,其中第 i 个整数表示图G 上编号为i 的点的权值为W i 。
输出格式:输出文件名为link .out 。
输出共1 行,包含2 个整数,之间用一个空格隔开,依次为图G 上联合权值的最大值
和所有联合权值之和。由于所有联合权值之和可能很大,[b]输出它时要对10007 取余。 [/b]
输入输出样例输入样例#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≤ 100 ;
对于60% 的数据,1 < n≤ 2000;
对于100%的数据,1 < n≤ 200 , 000 ,0 < wi≤ 10, 000 。
题中描述的距离为2可以转化为一个点的两个儿子的距离,所以权值总和为各个点的不同的两个儿子的权值之积。
导出公式:
a,b,c,d,e之间的距离都为2,sum=a(b+c+d+e)+b(a+c+d+e)+c(a+b+d+e)..... --> sum=a(s-a)+b(s-b)..... s=a+b+c+d+e
我们把一个节点的两个不同儿子的权值积称为关于某个点的权值,任意两个不同儿子的权值积的和称为关于某个点的权值之和,利用这个公式可以把O(n^2)求关于每个点权值之和的方法优化为O(n)。
在求第二问的时候,可以采用贪心的策略,求出关于某个点权值之和时,处理出它的所有儿子节点中权值最大的和次大的,这两个数的积就是关于这个点的权值的最大值。
似乎数据卡常,用vector超时。
代码:
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#define rep(q,p) for (int q=1;q<=p;q++)
#define ll long long
using namespace std;
const int maxn=2e5+5,md=1e4+7;
int n,x,y,w[maxn],tp;
ll ans,tot,sum,m1[maxn],m2[maxn];
vector<int>v[maxn];
inline void getint(int &_x)
{
_x=0;
char _ch;
for(_ch=getchar();_ch>'9'||_ch<'0';_ch=getchar());
for(;_ch<='9'&&_ch>='0';_ch=getchar())
_x=_x*10+_ch-48;
}
int main()
{
freopen("in.txt","r",stdin);
getint(n);
rep(i,n-1) getint(x),getint(y),v[x].push_back(y),v[y].push_back(x);
rep(i,n) getint(w[i]);
rep(i,n)
if (v[i].size()>=2)
{
sum=0;
for (int k=0;k<v[i].size();k++)
{
sum+=w[v[i][k]];
if (w[v[i][k]]>m1[i])
{
m1[i]=w[v[i][k]];
tp=k;
}
}
for (int k=0;k<v[i].size();k++) tot+=w[v[i][k]]*(sum-w[v[i][k]]),tot%=md;
for (int k=0;k<v[i].size();k++)
if (k!=tp && w[v[i][k]]>m2[i])
m2[i]=w[v[i][k]];
}
rep(i,n)
if (m1[i]*m2[i]>ans) ans=m1[i]*m2[i];
printf("%lld %lld\n",ans,tot);
return 0;
}
© stonechina0616 | Powered by LOFTER