洛谷P1351 [NOIP 2014 提高組] 聯合權值

洛谷題目傳送門

題目背景

NOIP2014 提高組 D1T2

題目描述

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

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

輸入格式

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

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

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

輸出格式

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

輸入輸出樣例 #1

輸入 #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\le 100$；
• 對于 $60\%$ 的數據，$1<n\le 2000$；
• 對于 $100\%$ 的數據，$1<n\le 2\times 10^5$，$0<W_i\le 10000$。

保證一定存在可產生聯合權值的有序點對。

思路詳解

雖然這個題目說他是一個圖，但由n-1條邊的連通圖可得他是一棵樹，思考如何求解出最大值與和。

最大值

首先考慮哪些點可以湊成一個聯合點對？？？由于只要距離為2，那顯然對于一個節點$u$，$u$的任意子節點$v$，都可以和$u$的其余所有子節點組成聯合點對，也可以和$u$的父親節點組成點對。那最大值就很顯然了：

1. $v$與其他子節點組合：顯然我們只需要找出最大值$d_1$與次大值$d_2$組合即可。
2. $v$與$u$的父親組合：直接找到最大值$d1$與$a_{f{a}_u}$組合即可。

和

與上面相同，我們只需要分為兩部分求解即可。具體如下：

1. $v$與$u$的父親組合：令$u$的所有子節點權值和為$su{m}_u$，則這一部分答案$an{s}_2=su{m}_u?a_{f{a}_u}$。
2. $v$與其他子節點組合：則這一部分的答案為$an{s}_3={\sum }_v{a}_v?(su{m}_u?a_v)$因為他不能與他自己組合。

但我們發現聯合點對是有序的，那我們是否輸出$2(an{s}_2+an{s}_3)$呢？？？雖然這樣樣例可以過，但我們只能得到0分的好成績，這是為何？我們發現$an{s}_3$其實已經相當于乘過2了，只有$an{s}_2$需要乘2。這就是水樣例的惡劣影響。

code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=5e5+5,mod=10007;
ll n,a[N];
ll h[N],to[N],ne[N],tot=0;
void add(ll u,ll v){//建邊tot++;to[tot]=v;ne[tot]=h[u];h[u]=tot;
}
ll d1[N],d2[N],ans1=0,sum[N],ans2=0,ans3=0;
//d1[u]為u的子節點的最大值，d2[u]為次大值，sum[u]為u的子節點的和。
void dfs(ll u,ll fa){d1[u]=-0x3f3f3f3f;d2[u]=-0x3f3f3f3f;//賦初值sum[u]=0;for(ll i=h[u];i;i=ne[i]){ll v=to[i];if(v==fa)continue;sum[u]=(sum[u]+a[v])%mod;if(a[v]>d1[u]){d2[u]=d1[u];d1[u]=a[v];}//更新最大值else if(a[v]>d2[u]){d2[u]=a[v];}//更新次大值dfs(v,u);}for(ll i=h[u];i;i=ne[i]){//求解ans3ll v=to[i];if(v==fa)continue;ans3=(ans3+a[v]*((sum[u]-a[v]+mod)%mod)%mod)%mod;}ans2=(ans2+sum[u]*a[fa]%mod)%mod;//求解ans2if(d1[u]==-0x3f3f3f3f&&d2[u]==-0x3f3f3f3f)return;//沒有子節點，不更新ans1ans1=max(ans1,max(d1[u]*d2[u],d1[u]*a[fa]));
}
int main(){cin>>n;for(ll i=1;i<=n-1;i++){ll x,y;cin>>x>>y;add(x,y);add(y,x);}for(ll i=1;i<=n;i++)cin>>a[i];sum[0]+=a[1];dfs(1,0);cout<<ans1<<' '<<(ans2*2+ans3)%mod;return 0;
}
/*高級樣例
5
1 2
1 3
2 4
2 5
1 2 4 6 5
*/