鏈接：https://ac.nowcoder.com/acm/contest/18072/A

牛妹有一張連通圖，由n個點和n-1條邊構(gòu)成，也就是說這是一棵樹，牛妹可以任意選擇一個點為根，根的深度為0，對于任意一個非根的點，我們將他到根節(jié)點路徑上的第一個點稱作他的父節(jié)點，例如1為根，1-4的；路徑為1-3-5-4時，4的父節(jié)點是5，并且滿足對任意非根節(jié)點，，整棵樹的價值，即所有點的深度和

牛妹希望這棵樹的W最小，請你告訴她，選擇哪個點可以使W最小

?題目：求樹所有節(jié)點的深度累加的最小值（選擇一個點為根）

思路：根據(jù)重心的定義，可以求出重心，直接以重心為根。

還有換根dp：先求出以1為根的答案,考慮x->y，dp[y]=dp[u]-son[y]+n-son[y];

#include <iostream> #include <cstdio> #include <fstream> #include <algorithm> #include <cmath> #include <deque> #include <vector> #include <queue> #include <string> #include <cstring> #include <map> #include <stack> #include <set> #include <cstdlib> #define INF 0x3f3f3f3f3f3f3f3f #define inf 0x3f3f3f3f #define FILL(a,b) (memset(a,b,sizeof(a))) #define re register #define lson rt<<1 #define rson rt<<1|1 #define lowbit(a) ((a)&-(a)) #define ios std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0); #define fi first #define rep(i,n) for(int i=0;(i)<(n);i++) #define rep1(i,n) for(int i=1;(i)<=(n);i++) #define se second #define scd(a) scanf("%d",&a) #define scdd(a,b) scanf("%d%d",&a,&b) #define scddd(a,b,c) scanf("%d%d%d",&a,&b,&c) #define ac cout<<ans<<"\n" #define F(x) ((x)/3+((x)%3==1?0:tb)) #define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2) using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll,ll> pii; int dx[4]= {-1,1,0,0},dy[4]= {0,0,1,-1}; const ll mod=1e9+7; const ll N =1e6+10; const double eps = 1e-4; //const double pi=acos(-1);int n; vector<int> g[N]; int dis[N]; int son[N]; int sum,ans; int dp[N]; void dfs1(int u,int f){son[u]=1;dis[u]=dis[f]+1;for(int v:g[u]){if(v==f) continue;dfs1(v,u);son[u]+=son[v];}sum+=(dis[u]-1); } void dfs_dp(int u,int f){for(int v:g[u]){if(v==f) continue;dp[v]=dp[u]-son[v]+n-son[v];dfs_dp(v,u);}ans=min(ans,dp[u]); } int main() {iosans=inf;cin>>n;for(int i=1;i<=n-1;i++){int x,y;cin>>x>>y;g[x].push_back(y);g[y].push_back(x);}dfs1(1,0);dp[1]=sum;ans=dp[1];dfs_dp(1,0);cout<<ans; }

總結(jié)

以上是生活随笔為你收集整理的换根dp求树所有节点的最小深度的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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