題目描述

無向連通圖?G?有?n?個點，n?1?條邊。點從?1?到?n?依次編號,編號為?i?的點的權值為?Wi?，每條邊的長度均為?1。圖上兩點?(u,v)?的距離定義為?u?點到?v?點的最短距離。對于圖?G?上的點對?(u,v)，若它們的距離為?2，則它們之間會產生?Wv?×Wu??的聯合權值。

請問圖?G?上所有可產生聯合權值的有序點對中，聯合權值最大的是多少？所有聯合權值之和是多少？

輸入格式

第一行包含?1?個整數?n。

接下來?n?1?行,每行包含?2?個用空格隔開的正整數?u,v，表示編號為?u?和編號為?v?的點之間有邊相連。

最后?1?行，包含?n?個正整數，每兩個正整數之間用一個空格隔開，其中第?i?個整數表示圖?G?上編號為?i?的點的權值為?Wi?。

輸出格式

輸出共?1?行，包含?2?個整數，之間用一個空格隔開,依次為圖?G?上聯合權值的最大值和所有聯合權值之和。由于所有聯合權值之和可能很大，輸出它時要對?10007?取余。

輸入輸出樣例

輸入?

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

輸出?

20 74

#include<bits/stdc++.h>
using namespace std;
const int mod=10007;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
typedef pair<int,int> pii;
#define int long longconst int N=1000010;vector<int>g[N];
int n;
int a[N];
int maxn,ans;void solve()
{cin>>n;int m=n-1;for(int i=0;i<m;i++) {int a,b;cin>>a>>b;g[a].push_back(b);g[b].push_back(a);}	for(int i=1;i<=n;i++)cin>>a[i];ans=0;int maxn=0,ans=0;for(int i=1;i<=n;i++){int sum1=0,ans1=0,ans2=0;for(auto t:g[i])sum1+=a[t];if(g[i].size()==1)continue;for(auto t:g[i]){if(a[t]>ans1){ans2=ans1;ans1=a[t];}else if(a[t]>ans2){ans2=a[t];}ans=(ans+a[t]*(sum1-a[t])%mod)%mod;}maxn=max(maxn,ans1*ans2);}cout<<maxn<<' '<<ans<<endl;
}
signed main()
{ int good_luck_to_you;ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);good_luck_to_you=1;//cin>>good_luck_to_you;while(good_luck_to_you--){solve();}return 0;
}

本題是關于樹的問題，剛開始我認為只要dfs，每一次找該點的下下一個點，然后枚舉就可以了，但是我忽略了對于我剛開始就隨便找了一個當作根，所以接下來的兄弟節點就不可能有聯合權值，但是他們也是符合條件的，所以我們只需要枚舉中間那個點就可以，只需要找到該點的鄰居節點的最大值和次大值，至于聯合權值的和，該點的鄰居節點肯定要和其他鄰居節點都要乘起來加和，所以我們可以算出來該點的鄰居節點的和sum，然后遍歷鄰居節點時（假如值為x)值就為x*(sum-x)。?

?