【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

【CSU 1079】树上的查询

// <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 register
using 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;
}

  

上一篇:[转载]java NIO详解


下一篇:如何查看kernel社区的变更历史