快乐树论
Description
?曾經(jīng)有一位偉大的皇帝，他擁有n座城池并用n-1條無向道路相連，每條道路均有一個(gè)確定的長度和兩個(gè)端點(diǎn)，保證城池與城池之間互達(dá)。有一天，皇帝決定將其中一條路拆掉，并重新將這條道路以同樣的長度搭在兩座城池之間，皇帝可能將這條路拆了又重新建在原處。現(xiàn)在皇帝想問問你，在只拆掉一條道路并重新建造一條同樣長的在兩座城池之間后，任意兩個(gè)城池之前的距離和最小為多少呢？
?
Input
?第一行輸入一個(gè)n代表皇帝有n座城池，接下來n-1行輸入a,b,c代表城池a,b之間有一條長為c的道路。 (2?≤?n?≤?5000, 1?≤?ai,?bi?≤?n,?ai?≠?bi,?1?≤?wi?≤?106)
?
Output
?輸出一行任意兩城池之間的最小距離和。
?
Sample Input
輸入樣例1： 3 1 2 2 1 3 4 輸入樣例2： 6 1 2 1 2 3 1 3 4 1 4 5 1 5 6 1 輸入樣例3： 6 1 3 1 2 3 1Sample Output
輸出樣例1： 12 輸出樣例2： 29 輸出樣例3： 825HINT
?
?實(shí)際輸入輸出中并沒有“輸入樣例1”， “輸出樣例1：” 之類 這種東西，這里只是為了多給幾組數(shù)據(jù)，讓大家更容易的理解用的
題解：
具體證明參考：https://blog.csdn.net/zhoufenqin/article/details/9821617
#include<bits/stdc++.h>#define fi first #define se second #define pb push_backusing namespace std;typedef long long ll; typedef pair<ll,ll> Pll;const ll LLMAX=2e18; const int MAXN=1e6+10;struct node{int u,v;ll w; }in[MAXN];ll dp[MAXN][3]; vector<Pll>G[MAXN];void dfs(int u,int pre){dp[u][0]=dp[u][1]=dp[u][2]=0;for(int i=0;i<G[u].size();i++){int v=G[u][i].fi,w=G[u][i].se;if(v==pre) continue;dfs(v,u);dp[u][2]+=dp[v][2]+dp[v][1]*dp[u][0]+dp[v][0]*dp[u][1]+dp[u][0]*dp[v][0]*w;dp[u][1]+=dp[v][1]+dp[v][0]*w;dp[u][0]+=dp[v][0]; }dp[u][0]++;dp[u][2]+=dp[u][1]; }void solve(int u,int pre,ll &ans){ans=min(ans,dp[u][1]);for(int i=0;i<G[u].size();i++){int v=G[u][i].fi,w=G[u][i].se;if(v==pre) continue;dp[v][1]=dp[v][1]+(dp[u][1]-dp[v][1]-w*dp[v][0])+(dp[u][0]-dp[v][0])*w;dp[v][0]=dp[u][0];solve(v,u,ans);} }int main(void) {ios::sync_with_stdio(false); cin.tie(0);ll n,ans=LLMAX; cin>>n; for(int i=1;i<n;i++){ll x,y,v; cin>>x>>y>>v; in[i].u=x,in[i].v=y,in[i].w=v;G[x].pb(Pll(y,v)),G[y].pb(Pll(x,v));}for(int i=1;i<n;i++){ll ans1=LLMAX,ans2=LLMAX,u=in[i].u,v=in[i].v,w=in[i].w;dfs(u,v); solve(u,v,ans1);ll len1=(n-dp[u][0])*ans1+dp[u][2];dfs(v,u); solve(v,u,ans2);ll len2=(n-dp[v][0])*ans2+dp[v][2];ans=min(ans,len1+len2+dp[u][0]*dp[v][0]*w);}cout<<ans<<endl;return 0; }?
總結(jié)
