D - Kay and Snowflake

思路：

樹的重心

利用重心的一個推論，樹的重心必定在子樹重心的連線上。

然后利用重心的性質，可知，如果有一顆子樹的大小超過整棵樹的大小的1/2，那么樹的重心一定在這顆子樹上。

利用以上兩條，可知：

如果沒有一顆子樹的大小超過整棵樹的大小的1/2，那么就可以以根節點為樹的重心，

不然就從 超過1/2大小的子樹 的重心 到 根節點 之間找整棵樹的重心。

因為不會找重復的點，所以退化的復雜度為O(n)

#include<bits/stdc++.h> using namespace std; #define fi first #define se second #define mp make_pair #define LL long long #define pb push_back #define pii pair<int, int> #define mem(a, b) memset(a, b, sizeof(a)) const int N = 3e5 + 5; vector<int>g[N]; int tot[N], ans[N], fa[N]; void dfs(int u) {tot[u] = 1;for (int i = 0; i < g[u].size(); i++) {dfs(g[u][i]);tot[u] += tot[g[u][i]];} ans[u] = u;for (int i = 0; i < g[u].size(); i++) {if(tot[g[u][i]] * 2 > tot[u]) ans[u] = ans[g[u][i]];}while((tot[u] - tot[ans[u]]) * 2 > tot[u]) ans[u] = fa[ans[u]]; } int main() {int n, u, q;scanf("%d%d", &n, &q);for (int i = 2; i <= n; i++) {scanf("%d", &fa[i]);g[fa[i]].pb(i);}dfs(1);while (q--) {scanf("%d", &u);printf("%d\n",ans[u]);}return 0; }

?

轉載于:https://www.cnblogs.com/widsom/p/8918581.html

總結

以上是生活随笔為你收集整理的Codeforces 686 D - Kay and Snowflake的全部內容，希望文章能夠幫你解決所遇到的問題。

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