首页 > 代码库 > 【CSU 1079】树上的查询
【CSU 1079】树上的查询
http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1079
现有一棵有N个顶点的树,顶点的标号分别为1, 2, …, N。对于每个形如a b k的询问,你需要回答在从点a到点b的路径上是否包含点k。
DFS序&欧拉序列 LCA-最近公共祖先
看完这两篇文章就会做了
首先找出a,b的最近公共祖先p(Because 树上路径→(a→p→b)),我们要找这条路上是否存在点k
转换:k要在p的子树中 && (a||b)任意一点在p的子树中.裸的欧拉序列子树查询.
加上inline register 280ms rank1
// <1079.cpp> - Wed Oct 19 08:25:53 2016// This file is made by YJinpeng,created by XuYike‘s black technology automatically.// Copyright (C) 2016 ChangJun High School, Inc.// I don‘t know what this program is.#include <iostream>#include <vector>#include <algorithm>#include <cstring>#include <cstdio>#include <cstdlib>#include <cmath>#define MOD 1000000007#define INF 1e9#define RG registerusing namespace std;typedef long long LL;const int N=100010;inline int gi() { register int w=0,q=0;register char ch=getchar(); while((ch<‘0‘||ch>‘9‘)&&ch!=‘-‘)ch=getchar(); if(ch==‘-‘)q=1,ch=getchar(); while(ch>=‘0‘&&ch<=‘9‘)w=w*10+ch-‘0‘,ch=getchar(); return q?-w:w;}int t,_t;int to[N<<1],ne[N<<1];int f[N][31],d[N],fr[N],be[N],en[N];inline void add(RG int u,RG int v){ to[++t]=v;ne[t]=fr[u];fr[u]=t; to[++t]=u;ne[t]=fr[v];fr[v]=t;}inline void dfs(RG int x,RG int fa,RG int de){ d[x]=de;be[x]=++_t;f[x][0]=fa; for(int o=fr[x];o;o=ne[o]) if(to[o]!=fa)dfs(to[o],x,de+1); en[x]=++_t;}inline bool IN(RG int x,RG int y){return be[x]>=be[y]&&be[x]<=en[y];}int main(){ freopen("1079.in","r",stdin); freopen("1079.out","w",stdout); int n,q; while(~scanf("%d",&n)){ _t=t=0;q=gi();memset(fr,0,sizeof(fr)); for(int i=1;i<n;i++)add(gi(),gi()); dfs(1,0,1); for(int j=1;j<=30;j++) for(int i=1;i<=n;i++)f[i][j]=f[f[i][j-1]][j-1]; while(q--){ int a=gi(),b=gi(),k=gi(),o=0,x=a,y=b; if(d[a]<d[b])swap(a,b); while(d[a]>d[b]){ while(d[f[a][o]]>=d[b])o++; a=f[a][o-1];o=0; }o=0; while(f[a][0]!=f[b][0]){ while(f[a][o]!=f[b][o])o++; a=f[a][o-1];b=f[b][o-1];o=0; } int p=a==b?a:f[a][0]; printf(IN(k,p)?(IN(x,k)||IN(y,k)?"YES":"NO"):"NO"); printf("\n"); }printf("\n"); } return 0;}
【CSU 1079】树上的查询
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。