題目鏈接:傳送門

題目大意:給你n個點，n-1條邊連接所有點構成一棵樹，1是樹根，有m次詢問，對于每次詢問的點x，在x及x的子樹中找出一個點，使刪去這個點，所得包含元素最多的聯通分塊

　　　　 所含有的點的個數<=原x及x子樹的點之和的1/2。輸出這個點。

題目思路:比賽時想了一種方法，遞歸求每個點的連通度然后找子樹所含點中最大的聯通度向上不斷更新，不過方法錯了，比如給一條鏈的話，詢問樹根1，答案就錯了

　　　　 后來補題的時候始終是在考慮怎么樣將子樹中刪去一個點能產生最大連通塊所含點數保存并更新上去，在這就卡住了。看了這篇博客后，恍然大悟，實際上

　　　　 遞歸到葉子節點，那么對于所有葉子節點的答案就是它本身，既然邊界情況已出，我們只需要向上更新即可。(真正的標簽是 樹形DP)

　　　　 在這之前還有一個結論: 對于任一點x，答案一定是在它和它的子樹當中。

　　　　 我們從x向下遞歸最后會得到一個包含點數最多的一個聯通分塊，并且同時得到x與此聯通分塊直接相連的一個子節點，既然是遞歸，

　　　　 那么再向上傳遞聯通分塊所包含點數的同時，答案也同時向上傳遞，那么這時x的答案是子節點的答案（有可能答案對于x不合法），如果答案不合法，利用

　　　　 上面的結論，找答案節點的父節點即可，直到滿足條件為止。

#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <algorithm> #include <cstring> #include <stack> #include <cctype> #include <queue> #include <string> #include <vector> #include <set> #include <map> #include <climits> #define lson root<<1,l,mid #define rson root<<1|1,mid+1,r #define fi first #define se second #define ping(x,y) ((x-y)*(x-y)) #define mst(x,y) memset(x,y,sizeof(x)) #define mcp(x,y) memcpy(x,y,sizeof(y)) using namespace std; #define gamma 0.5772156649015328606065120 #define MOD 1000000007 #define inf 0x3f3f3f3f #define N 300005 #define maxn 1005 typedef pair<int,int> PII; typedef long long LL;int n,m,k,x,num,y; int pre[N],ans[N],Size[N]; struct Node{int to,next; }node[N<<1];int hcnt,head[N];inline void add(int x,int y){node[hcnt].to=y;node[hcnt].next=head[x];head[x]=hcnt++; } void dfs(int x,int fa){int t=x; ///t表示所含點數最多的連通分量與x直接相連的點Size[x]=1; ///Size表示當前節點一共包含多少點數int mx=0; for(int i=head[x];~i;i=node[i].next){int e=node[i].to;if(e==fa)continue;dfs(e,x);Size[x]+=Size[e];if(Size[e]>mx){mx=Size[e];t=e;}}ans[x]=t==x?x:ans[t];while(ans[x]!=x&&Size[x]-Size[ans[x]]>Size[x]/2){ans[x]=pre[ans[x]];} } int main(){int i,j,group,v;scanf("%d%d",&n,&m);mst(head,-1);for(i=2;i<=n;++i){scanf("%d",&x);add(i,x);add(x,i);pre[i]=x;}dfs(1,-1);while(m--){scanf("%d",&x);printf("%d\n",ans[x]);}return 0; }

?

轉載于:https://www.cnblogs.com/Kurokey/p/5615212.html

總結

以上是生活随笔為你收集整理的Codeforces Round #359 (Div. 2) D. Kay and Snowflake的全部內容，希望文章能夠幫你解決所遇到的問題。

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