正題

評(píng)測(cè)記錄:https://www.luogu.org/recordnew/lists?uid=52918&pid=P1351

---

題目大意

一棵樹(shù)，每個(gè)點(diǎn)有權(quán)值，求兩個(gè)距離為2的點(diǎn)使權(quán)值之積最大和所以這種點(diǎn)對(duì)的權(quán)值之積的和。

---

解題思路

分為兩種情況：
1.一個(gè)點(diǎn)是另一個(gè)點(diǎn)的爺節(jié)點(diǎn)，這時(shí)候在遍歷時(shí)保存爺節(jié)點(diǎn)就好了。
2.一個(gè)點(diǎn)是另一個(gè)點(diǎn)的兄弟，這時(shí)候在一個(gè)點(diǎn)跑兒子的時(shí)候計(jì)算就好。

---

code

#include<cstdio> #include<algorithm> #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].to=y;a[tot].next=ls[x];ls[x]=tot; } void dp(ll x,ll fa1,ll fa2)//第一種情況 {ans=(ans+w[x]*w[fa2])%10007;maxs=max(maxs,w[x]*w[fa2]);for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(y!=fa1) dp(y,x,fa1);} } void dp2(ll x,ll fa)//第二種情況 {ll max1=0,max2=0,sum=0;for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(y!=fa){dp2(y,x);ans=(ans+sum*w[y]%10007)%10007;sum+=w[y];}if(w[y]>max1) swap(max1,max2),max1=w[y];else if(w[y]>max2) max2=w[y];}maxs=max(maxs,max1*max2); } int main() {scanf("%lld",&n);for(ll i=1;i<n;i++){scanf("%lld%lld",&x,&y);addl(x,y);addl(y,x);}for(ll i=1;i<=n;i++)scanf("%lld",&w[i]);dp(1,0,0);dp2(1,0);printf("%lld %lld",maxs,ans*2%10007); }

總結(jié)

以上是生活随笔為你收集整理的P1351-联合权值【树形结构】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。