首页 > 代码库 > Hdu 4916 Count on the path
Hdu 4916 Count on the path
题意:给定一棵树顶点标号为连续的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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。