意甲冠軍：鑒于一棵樹的頂點標簽為連續1~n,不是每個網上查詢a-b最小的圓點標簽路徑

這題想了好久，如果1為根節點。

首先如果a-b只是根節點1。答案一定是1。

否則我們用fa[i]表示i節點的父親，belong[i]表示i節點祖先是belong[i],且belong[i]是根節點兒子。這樣我們能夠預處理出ans[i]表示在belong[i]這顆子樹中除去i到根節點的路徑中最小的值。統計答案就可以。

討論時需注意一些細節，首先處理出每一個節點的最小值和次小值，分別來源于它的兩個子樹。不包含節點本身。統計ans[i]的時候要在belong[i]中討論且先統計不包含i本身子樹的部分，顯然ans[i]能夠等于ans[fa[i]]。假設以i的子樹(包含節點)的最小值和fa[i]的最小值相等，顯然ans[i]能夠等于fa[i]的次小值，由于i和fa[i]次小值節點不在一顆子樹上;假設以i的子樹(包含節點)的最小值和fa[i]的次小值相等，顯然ans[i]能夠等于fa[i]的最小值。最后再比較ans[i]和i本身子樹最小值來更新ans[i]。

統計出ans[i]后每次詢問O(1)回答就可以。

代碼https://github.com/mlz000/hdu/blob/master/4916(%E6%A0%91%E4%B8%8A%E5%A5%BD%E9%A2%98).cpp

#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; const int N=1000005,inf=1e9; int n,q,tot,min3,belong[N],Q[N],head[N],next[N<<1],to[N<<1],fa[N],ans[N]; pair<int,int>a[N]; #define mp make_pair void add(int u,int v){to[++tot]=v;next[tot]=head[u];head[u]=tot; } int ask(int x,int y){if(x>y) swap(x,y);if(x==1 || y==1){if(x==1 && y==1) return a[1].first;if(min(belong[y],ans[belong[y]])!=a[1].first) return a[1].first;return min(a[1].second,ans[y]);}else{if(belong[x]==belong[y]) return 1;int tmp1=min(belong[x],a[belong[x]].first),tmp2=min(belong[y],a[belong[y]].first);if(min(tmp1,tmp2)!=a[1].first) return a[1].first;int now=0;if(tmp1!=a[1].second && tmp2!=a[1].second) now=a[1].second;else now=min3;now=min(now,min(ans[x],ans[y]));return now;} } int main(){while(~scanf("%d%d",&n,&q)){int last=0;tot=0;memset(head,0,sizeof(head));for(int i=1,x,y;i<n;++i){scanf("%d%d",&x,&y);add(x,y);add(y,x);}Q[1]=1;for(int h=1,r=1;h<=r;++h){int now=Q[h];for(int i=head[now];i;i=next[i]){if(to[i]==fa[now]) continue;if(belong[now]) belong[to[i]]=belong[now];else belong[to[i]]=to[i];fa[to[i]]=now;Q[++r]=to[i];}}for(int i=1;i<=n;++i) a[i]=mp(inf,inf);for(int i=n;i>=1;--i){int now=Q[i];int tmp=min(now,a[now].first);int father=fa[now];if(tmp<a[father].second){a[father].second=tmp;if(a[father].second<a[father].first) swap(a[father].first,a[father].second);}}min3=inf;for(int i=head[1];i;i=next[i]){int now=min(to[i],a[to[i]].first);if(now!=a[1].first && now!=a[1].second) min3=min(min3,now);}for(int i=2;i<=n;++i){int minnow=min(Q[i],a[Q[i]].first);int father=fa[Q[i]];if(father!=1){ans[Q[i]]=ans[father];if(minnow==a[father].first) ans[Q[i]]=min(ans[Q[i]],a[father].second);else ans[Q[i]]=min(ans[Q[i]],a[father].first);}else ans[Q[i]]=inf;}for(int i=2;i<=n;++i) ans[i]=min(ans[i],a[i].first);while(q--){int x,y;scanf("%d%d",&x,&y);x=x^last;y=y^last;last=ask(x,y);printf("%d\n",last);}}return 0; }

版權聲明：本文博客原創文章。博客，未經同意，不得轉載。

總結

以上是生活随笔為你收集整理的Hdu 4916 Count on the path的全部內容，希望文章能夠幫你解決所遇到的問題。

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