NOIP2014 联合权值

题目描述

无向连通图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





说明

NOIP2014 联合权值 - 906229046 - 906229046的博客

本例输入的图如上所示,距离为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