砍树枝 冲刺noip

砍树枝
代码测试区
题目：
这天，CD 作为moreD 的宠物，又被残酷地训练爬树了，moreD 保证了这棵树满足从任意一个点出发，CD 都能走到所有的点，CD 每天都要爬过所有的点才能回家吃饭。经过一天又一天残酷的训练以后，CD 已经忍无可忍了，于是CD 会愤怒地误伤一条树枝，一条树枝被误伤以后就不可以再走了。当然，CD 不符合宠物法则的行动怎么会逃过moreD 的眼睛，moreD 决定，每当CD 误伤一条树枝，他都会再重新加一条树枝，可是他不知道加完以后，这只宠物是否还能从任意一个点出发到达所有的点，要是不能，岂不是让这只宠物得逞了么？问题是，现在moreD 也不知道CD 最终会误伤哪一条树枝，于是现在moreD臆测出了许多种可能，你要告诉moreD：如果CD 误伤了第z 条边，他再在编号为x 的点和编号为y 的点之间加一条边，CD 是否能得逞。
输入格式：
第一行一个正整数n，表示节点个数。接下来n-1 行，每行两个正整数x，y，表示原来树上存在一条连接编号为x的节点和编号为y 的节点的边。第n+1 行一个正整数Q，表示询问次数。接下来Q 行，每行三个正整数x，y，z，表示一个询问（含义如题所示）。
输出格式：
输出共Q 行。对于每一个询问，如果CD 会得逞就输出YES，否则输出NO。
样例输入1：:
5
1 2
2 3
2 4
4 5
3
2 5 3
2 3 1
1 5 2
样例输出1：
NO
YES
YES
数据范围：
对于20%的数据保证n，Q≤1000。对于另外20%的数据保证n，Q≤10000 且树为随机生成。对于70%的数据保证n，Q≤200000。对于100%的数据保证n≤200000,Q≤2000000。

题解：
知识点： dfs序
讲解：
这一题太坑了，一开始看是lca结果gg了，后面想了想处理点的重合才是lca（有兴趣了解的点这），边就不是了，边应该用dfs序。
分析一下题目，如果CD破坏了一条边的话，那么整个树就变成了两个联通块，如果moreD加的一条边可以连通两个联通块的话那么CD就不能得逞，如果不能连通的话就可以得逞。现在问题就是如何判断一条边能否连通两个联通块，很明显如果边的两点分别在两个联通块的话那就肯定可以联通了，现在我们就要判断两个点是否分别在两个联通块。再看一下这两个连通块的特点，我们可以确定这两个联通块一定是两棵树，而且一棵还是一棵子树，那么很容易想到dfs序，因为在dfs序同一棵树中的dfs序是连续的，这样我们只要找到分割后的子树的dfs序，看一下两个点的dfs序是否一个在里面另一个不在。
因为这一题的原因我们不知道所给的边哪个是父亲哪个是儿子，这样哪个是子树也不好确定（因为儿子在的联通块一定是子树，好好想想），不过我们知道儿子的dfs序范围一定比父亲小，所以我们只要选in中最大的，out中的最小的就好了。
上代码：

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int in[200100],out[200100],head[400100],Next[400100],ver[400100],size=0,n,x[200100],y[200100],vist[200100];
void add(int x,int y)
{
	size++;
	Next[size]=head[x];
	head[x]=size;
	ver[size]=y;
	return ;
}
void dfs(int x)
{
	size++;//dfs序常规++ 
	in[x]=size;//统计一下这一个点开始的dfs序 
	for(int i=head[x];i;i=Next[i])
	{
		int y=ver[i];
		if(vist[y]==1)
			continue;
		vist[y]=1;
		dfs(y);
	}
	out[x]=size;//统计一下结束的dfs序，这样从开始到结束就是以它为根的子树的各个点的dfs序 
}
int main()
{
	int m;
	scanf("%d",&n);
	for(int i=1;i<n;i++)//读入树 
	{
		scanf("%d %d",&x[i],&y[i]);
		add(x[i],y[i]);
		add(y[i],x[i]);
	}
	size=0;//初始化一下size 
	dfs(1);//dfs一下确定dfs序 
	scanf("%d",&m);//开始询问 
	for(int i=1;i<=m;i++)
	{
		int x1,y1,z,l,r;
		scanf("%d %d %d",&x1,&y1,&z);//输入数据 
		l=max(in[y[z]],in[x[z]]);//确定子树 
		r=min(out[y[z]],out[x[z]]);//确定子树 
		if(!(l<=in[x1] && out[x1]<=r) && l<=in[y1] && out[y1]<=r)//点x1在，y1不在 
			printf("NO\n");
		else if(!(l<=in[y1] && out[y1]<=r) && l<=in[x1] && out[x1]<=r)//点y1在，x1不在 
				printf("NO\n");
			else printf("YES\n");//剩下就是YES了 
	}
	return 0;
}

希望大家都可以AC。noip我来了。