題干：

Avin has two trees which are not connected. He asks you to add an edge between them to make them connected while minimizing the function?∑ni=1∑nj=i+1dis(i,j)∑i=1n∑j=i+1ndis(i,j), where?dis(i,j)dis(i,j)?represents the number of edges of the path from?ii?to?jj. He is happy with only the function value.

Input

The first line contains a number?n?(2<=n<=100000)n?(2<=n<=100000). In each of the following?n?2n?2?lines, there are two numbers?uu?and?vv, meaning that there is an edge between?uuand?vv. The input is guaranteed to contain exactly two trees.

Output

Just print the minimum function value.

Sample Input

3 1 2

Sample Output

4

題目大意：

給定n個點和n-2條邊，已知這是兩棵樹。讓你在每棵樹中任選一點，加一條邊，使得變成一棵樹，要求使得樹中任意兩點的距離之和最小，求出這個最小值。

解題報告：

以邊為單位統計貢獻就行了，注意最后統計的是任意兩點之間的距離和，而不是第一棵樹的任意一點和第二棵樹的任意一點之間的距離和。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define FF first #define SS second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e5 + 5; int n; vector<int> vv[MAX]; int f[MAX]; ll dp[MAX],size[MAX]; int getf(int v) {return f[v] == v ? v : f[v] = getf(f[v]); } void dfs1(int cur,int fa) {int up = vv[cur].size();size[cur] = 1;for(int i = 0; i<up; i++) {int v = vv[cur][i];if(v == fa) continue;dfs1(v,cur);size[cur] += size[v];dp[cur] += dp[v] + size[v];} } void dfs2(int cur,int fa,ll allsize) {int up = vv[cur].size();for(int i = 0; i<up; i++) {int v = vv[cur][i];if(v == fa) continue;dp[v] += dp[cur]-dp[v]-2*size[v]+allsize; // dp[v] += size[cur] - size[v] + dp[cur] - dp[v];大錯特錯啊，可以再想想dfs2(v,cur,allsize);} } int main() {cin>>n;for(int i = 1; i<=n; i++) f[i] = i;for(int u,v,i = 1; i<=n-2; i++) {scanf("%d%d",&u,&v);vv[u].pb(v),vv[v].pb(u);u=getf(u),v=getf(v);f[v] = u;}vector<int> rt;for(int i = 1; i<=n; i++) {if(f[i] == i) rt.pb(i);}dfs1(rt[0],-1);dfs2(rt[0],-1,size[rt[0]]);dfs1(rt[1],-1);dfs2(rt[1],-1,size[rt[1]]);ll mi0 = 1e18,mi1=1e18;ll tmp = 0; for(int i = 1; i<=n; i++) {if(getf(f[i]) == getf(f[rt[0]])) mi0 = min(mi0,dp[i]);else mi1 = min(mi1,dp[i]);tmp += dp[i];}printf("%lld\n",tmp/2 + size[rt[0]]*size[rt[1]]+mi0*size[rt[1]]+mi1*size[rt[0]]);return 0 ; }

?

總結

以上是生活随笔為你收集整理的【HDU - 6567】Cotree（树形dp，思维）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。