首页 > 代码库 > 【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】树上的查询