之前都看過有換根dp，一直不知道是啥意思，本來弱弱樹形dp都不太熟悉，不過今天工數課的時候突然想看一下，寫個板子題練練吧。

對于我的理解，換根的題目一般是根不確定，而求得答案與根是誰有關，而且通過暴力枚舉每個點為根節點即可得到答案。
這時候如果我們發現當該點的信息能夠通過父節點的信息遞推出來，那么我們可以考慮嘗試換根dp，畢竟換根dp的本質還是遞推，只不過通過父節點的信息遞推本節點。

[POI2008]STA-Station

不難發現如果我們知道以父節點為根所有深度和那么該節點相對于父親來說，該節點子樹的深度比以父節點為根時的深度要小1，而不在該節點子樹中的節點深度要比以父節點是根時的深度大1，由此得出以下遞推關系
$f_{son}=f_u+n?siz{e}_{son}?siz{e}_{son}$

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) //#pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<queue> #include<random> #include<bitset> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<unordered_map> #include<unordered_set> using namespace std; typedef long long ll; typedef pair<int,int> pii; const int N=1000010; int h[N],e[2*N],ne[2*N],idx; int n; ll dep[N]; int sz[N]; ll f[N]; int res=1; void dfs1(int u,int fa) {sz[u]=1;for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];if(j==fa) continue;dep[j]=dep[u]+1;dfs1(j,u); sz[u]+=sz[j];} } void dfs2(int u,int fa) {for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];if(j==fa) continue;f[j]=f[u]+sz[1]-sz[j]-sz[j];if(f[j]>f[res]) res=j;dfs2(j,u);}} void add(int a,int b) {e[idx]=b;ne[idx]=h[a];h[a]=idx++; } int main() {IO;int T=1;//cin>>T;while(T--){cin>>n;memset(h,-1,sizeof h);for(int i=1;i<n;i++){int a,b;cin>>a>>b;add(a,b),add(b,a);}dfs1(1,-1);for(int i=1;i<=n;i++) f[1]+=dep[i];dfs2(1,-1);cout<<res<<'\n';}return 0; }

總結

以上是生活随笔為你收集整理的[POI2008]STA-Station的全部內容，希望文章能夠幫你解決所遇到的問題。

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