首页 > 代码库 > 【树链剖分】【dfs序】【LCA】【分类讨论】Codeforces Round #425 (Div. 2) D. Misha, Grisha and Underground
【树链剖分】【dfs序】【LCA】【分类讨论】Codeforces Round #425 (Div. 2) D. Misha, Grisha and Underground
一棵树,q次询问,每次给你三个点a b c,让你把它们选做s f t,问你把s到f +1后,询问f到t的和,然后可能的最大值是多少。
最无脑的想法是链剖线段树……但是会TLE。
LCT一样无脑,但是少一个log,可以过。
正解是分类讨论,
如果t不在lca(s,f)的子树内,答案是dis(lca(s,f),f)。
如果t在lca(s,f)的子树内,并且dep(lca(s,t))>dep(lca(f,t)),答案是dis(lca(s,t),f);
否则答案是dis(lca(f,t),f)。
#include<cstdio> #include<algorithm> using namespace std; #define N 100010 int n,m,ans; int v[N<<1],next[N<<1],first[N],en; void AddEdge(int U,int V) { v[++en]=V; next[en]=first[U]; first[U]=en; } int fa[N],dep[N],top[N],son[N],siz[N]; int Ls[N],Rs[N],tot; void dfs(int U) { siz[U]=1; for(int i=first[U];i;i=next[i]) if(v[i]!=fa[U]) { fa[v[i]]=U; dep[v[i]]=dep[U]+1; dfs(v[i]); siz[U]+=siz[v[i]]; if(siz[v[i]]>siz[son[U]]) son[U]=v[i]; } } void df2(int U) { Ls[U]=++tot; if(son[U]) { top[son[U]]=top[U]; df2(son[U]); } for(int i=first[U];i;i=next[i]) if(v[i]!=fa[U]&&v[i]!=son[U]) { top[v[i]]=v[i]; df2(v[i]); } Rs[U]=tot; } int lca(int U,int V) { while(top[U]!=top[V]) { if(dep[top[U]]<dep[top[V]]) swap(U,V); U=fa[top[U]]; } if(dep[U]>dep[V]) swap(U,V); return U; } const int c[7][4]={{0,0,0,0},{0,1,2,3},{0,1,3,2},{0,2,1,3},{0,2,3,1},{0,3,1,2},{0,3,2,1}}; int calc(int U,int V){ int tmp=dep[lca(U,V)]; return dep[U]+dep[V]-tmp-tmp+1; } int main() { int b[4],x; scanf("%d%d",&n,&m); for(int i=2;i<=n;++i) { scanf("%d",&x); AddEdge(x,i); AddEdge(i,x); } top[1]=dep[1]=1; dfs(1); df2(1); for(int i=1;i<=m;++i){ int ans=0; for(int j=1;j<=3;++j){ scanf("%d",&b[j]); } for(int j=1;j<=6;++j){ int lcasf=lca(b[c[j][1]],b[c[j][2]]); if(Ls[b[c[j][3]]]<Ls[lcasf] || Ls[b[c[j][3]]]>Rs[lcasf]){ ans=max(ans,calc(lcasf,b[c[j][2]])); } else{ int lcast=lca(b[c[j][1]],b[c[j][3]]); int lcaft=lca(b[c[j][2]],b[c[j][3]]); if(dep[lcast]>dep[lcaft]){ ans=max(ans,calc(lcast,b[c[j][2]])); } else{ ans=max(ans,calc(lcaft,b[c[j][2]])); } } } printf("%d\n",ans); } return 0; }
【树链剖分】【dfs序】【LCA】【分类讨论】Codeforces Round #425 (Div. 2) D. Misha, Grisha and Underground
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。