县网站建设,云盘做网站文件,云主机与云电脑区别,建什么网站容易挣钱正题
评测记录:https://www.luogu.org/recordnew/lists?uid52918pidP1351 题目大意
一棵树#xff0c;每个点有权值#xff0c;求两个距离为2的点使权值之积最大和所以这种点对的权值之积的和。 解题思路
分为两种情况#xff1a; 1.一个点是另一个点的爷节点52918pidP1351 题目大意
一棵树每个点有权值求两个距离为2的点使权值之积最大和所以这种点对的权值之积的和。 解题思路
分为两种情况 1.一个点是另一个点的爷节点这时候在遍历时保存爷节点就好了。 2.一个点是另一个点的兄弟这时候在一个点跑儿子的时候计算就好。 code
#includecstdio
#includealgorithm
#define N 200010
#define ll long long
using namespace std;
struct line{ll to,next;
}a[N*2];
ll n,x,y,maxs,ls[N],tot,w[N],ans;
void addl(ll x,ll y)
{a[tot].toy;a[tot].nextls[x];ls[x]tot;
}
void dp(ll x,ll fa1,ll fa2)//第一种情况
{ans(answ[x]*w[fa2])%10007;maxsmax(maxs,w[x]*w[fa2]);for(ll ils[x];i;ia[i].next){ll ya[i].to;if(y!fa1) dp(y,x,fa1);}
}
void dp2(ll x,ll fa)//第二种情况
{ll max10,max20,sum0;for(ll ils[x];i;ia[i].next){ll ya[i].to;if(y!fa){dp2(y,x);ans(anssum*w[y]%10007)%10007;sumw[y];}if(w[y]max1) swap(max1,max2),max1w[y];else if(w[y]max2) max2w[y];}maxsmax(maxs,max1*max2);
}
int main()
{scanf(%lld,n);for(ll i1;in;i){scanf(%lld%lld,x,y);addl(x,y);addl(y,x);}for(ll i1;in;i)scanf(%lld,w[i]);dp(1,0,0);dp2(1,0);printf(%lld %lld,maxs,ans*2%10007);
}
