树分治

树的重心

我们选取一个点，要求将其删去后，结点最多的树的结点个数最小，这个点被
称为“树的重心”。

POJ1644 // Size[u] 代表以节点u为根的子树节点个数 // dp[u] 代表去除u节点后最大子树的节点个数 const int maxn = 2e4+100; vector<int> G[maxn]; int dp[maxn]; int Size[maxn]; int n; int ans; void dfs(int u,int fa){ dp[u] = Size[u] = 0; for(int i = 0;i < G[u].size(); ++i){ if(fa==G[u][i])continue; dfs(G[u][i],u); // sum += tmp; Size[u] += Size[G[u][i]]; dp[u] = max(dp[u],Size[G[u][i]]); } Size[u]++; dp[u] = max(n-Size[u],dp[u]); if(dp[u] < dp[ans]) ans = u; } int main(void) { int T; cin>>T; while(T--){ scanf("%d",&n); for(int i = 1;i <= n; ++i) G[i].clear(); for(int i = 1;i <= n-1; ++i){ int u,v; scanf("%d%d",&u,&v); G[u].push_back(v); G[v].push_back(u); } ans = 0; dp[0] = INF; dfs(1,-1); printf("%d %d\n",ans,dp[ans]); } return 0; }

应用树的重心的特性，即从树的重心开始树的点分治求解一些关于树的分治有关的问题

POJ1741

typedef pair<int,int> P; const int maxn = 1e4+100; vector<P> G[maxn]; int n,k; int size[maxn]; int dp[maxn]; bool vis[maxn]; int depth[maxn]; int deep[maxn]; // 求重心 void getroot(int u,int fa,int allnode,int &root){ size[u] = 1; dp[u] = 0; for(int i = 0;i < G[u].size(); ++i){ int v = G[u][i].FI; if(vis[v] || v == fa) continue; getroot(v,u,allnode,root); size[u] += size[v]; dp[u] = max(dp[u],size[v]); } dp[u] = max(dp[u],allnode-size[u]); if(dp[u] < dp[root]) {root = u;} } void dfsdepth(int u,int fa){ deep[++deep[0]] = depth[u]; size[u] = 1; for(int i = 0;i < G[u].size(); ++i){ int v = G[u][i].FI; if(vis[v]||v == fa) continue; depth[v] = depth[u] + G[u][i].SE; dfsdepth(v,u); size[u] += size[v]; } } int cal(int u,int d){ depth[u] = d; deep[0] = 0; dfsdepth(u,-1); sort(deep+1,deep+deep[0]+1); int ans = 0; for(int l = 1, r = deep[0];l < r; ){ if(deep[l]+deep[r] <= k){ ans += r-l; l++;} else r--; } return ans; } int work(int u){ vis[u] = 1; int ans = 0; // dfssize(u,-1); ans += cal(u,0); for(int i = 0;i < G[u].size(); ++i){ int v = G[u][i].FI; if(vis[v]) continue; ans -= cal(v,G[u][i].SE); int root = 0; getroot(v,u,size[v],root); // cout<<root<<endl; ans += work(root); } return ans; } int main(void) { while(scanf("%d%d",&n,&k)!=EOF&&n&&k){ memset(vis,0,sizeof(vis)); for(int i = 1;i <= n; ++i) G[i].clear(); for(int i = 1;i < n; ++i){ int u,v,w; scanf("%d%d%d",&u,&v,&w); G[u].Pb(P(v,w)); G[v].Pb(P(u,w)); } int root = 0; dp[root] = INF; getroot(1,-1,n,root); int ans = work(root); printf("%d\n",ans); } return 0; }