題意是給你一棵樹，然后詢問一個點，以這個點為根節點的樹的重心是多少
首先第一眼看上去感覺是維護子樹信息，感覺是dfs序，但是死活想不出應該維護什么值。后來學習了下q神的方法，原來直接樹形dp搞就行了呀，先算出每個子樹的節點個數，然后找里面最大的一棵子樹，重心必然在這棵子樹上（很明顯的，因為重心是刪除它之后，剩下的子樹里面節點最大的最小，所以重心應該是在最大的子樹里面），然后必然是在最大的子樹的重心的上面，這也是顯然的，所以可以直接從最大的子樹的重心往上，直到找到第一個點滿足num[res[u]]≥num[u]?num[res[u]]就是答案了

---

代碼

#include <map> #include <set> #include <stack> #include <queue> #include <cmath> #include <string> #include <vector> #include <cstdio> #include <cctype> #include <cstring> #include <sstream> #include <cstdlib> #include <iostream> #include <algorithm> #pragma comment(linker, "/STACK:102400000,102400000")using namespace std; #define MAX 300005 #define MAXN 6005 #define maxnode 15 #define sigma_size 30 #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define lrt rt<<1 #define rrt rt<<1|1 #define middle int m=(r+l)>>1 #define LL long long #define ull unsigned long long #define mem(x,v) memset(x,v,sizeof(x)) #define lowbit(x) (x&-x) #define pii pair<int,int> #define bits(a) __builtin_popcount(a) #define mk make_pair #define limit 10000//const int prime = 999983; const int INF = 0x3f3f3f3f; const LL INFF = 0x3f3f; const double pi = acos(-1.0); //const double inf = 1e18; const double eps = 1e-8; const LL mod = 1e9+7; const ull mx = 133333331;/*****************************************************/ inline void RI(int &x) {char c;while((c=getchar())<'0' || c>'9');x=c-'0';while((c=getchar())>='0' && c<='9') x=(x<<3)+(x<<1)+c-'0';} /*****************************************************/int fa[MAX]; int num[MAX]; int res[MAX]; vector<int> v[MAX];void dfs1(int u){num[u]=1;for(int i=0;i<v[u].size();i++){int vv=v[u][i];dfs1(vv);num[u]+=num[vv];} }void dfs2(int u){int mx=0;res[u]=u;for(int i=0;i<v[u].size();i++){int vv=v[u][i];dfs2(vv);if(num[vv]>=num[v[u][mx]]) mx=i;}if(v[u].size()>0){res[u]=res[v[u][mx]];while(res[u]!=u){if(num[res[u]]>=num[u]-num[res[u]]) break;res[u]=fa[res[u]];}} } int main(){int n,q;while(cin>>n>>q){for(int i=1;i<=n;i++) v[i].clear();for(int i=2;i<=n;i++){scanf("%d",&fa[i]);v[fa[i]].push_back(i);}dfs1(1);dfs2(1);while(q--){int a;scanf("%d",&a);printf("%d\n",res[a]);}}return 0; }

總結

以上是生活随笔為你收集整理的Codeforces 685BKay and Snowflake（树形dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

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