题意简述

题目链接

　　给定一棵边权均为1的树，m个询问，每次给出五个参数x,y,a,b,k，其中x≠y，连一条新的无向边(x,y)，询问a,b两点间是否存在一条长度为k的路径，路径可以重复经过某些点或某些边。

算法概述

　　这道题与有异曲同工之处。区别在于本题是在树上连新边后询问，而后者是在图上直接询问。

　　对于每个询问，首先如果不看这条新边，则点对(a,b)的最短路径有且仅有一条，记为dis(a,b)，则若k>=dis(a,b)且k≡dis(a,b)(mod 2)（即两者奇偶性相同），则必然有解，否则无解。

　　然后把这条新边加上，则(a,b)的最短路径组成有三种情况：

　　第一个分类标准是是否经过这条新边，若不经过，则①dis(a,b)；

　　若经过，则再看从哪个方向过这条边，若是x->y，则②dis(a,x)+(x,y)+dis(y,b)；

　　若是y->x，则③dis(a,y)+(y,x)+dis(x,b)。

　　然后分别判断这三条路径是否满足条件即可。只要有一条满足就有解，否则若三条均不满足则无解。

　　求树上任意两点间的最短路径可以先预处理根节点到每个点的最短路径d，然后用lca解决，下面的代码用树链剖分求解。由于这题权值在边上，故：

　　dis(u,v)=d[u]+d[v]-2*d[lca(u,v)]。

　　时间复杂度O(mlogn)。

参考代码

#include 
#include 
#include 
#include 
using namespace std;
const int N=1e5+10;

struct Edge{
	int to,next,w;
}edge[N<<1];int idx;
int h[N];

void add_edge(int u,int v,int w){edge[++idx]={v,h[u],w};h[u]=idx;}

int dep[N],fa[N],son[N];
int top[N],siz[N],dis[N];
int n,m;

void dfs1(int p,int f)
{
	fa[p]=f;
	dep[p]=dep[f]+1;
	siz[p]=1;
	int max_son=0;
	for(int i=h[p];~i;i=edge[i].next)
	{
		int to=edge[i].to,w=edge[i].w;
		if(to==f)continue;
		dis[to]=dis[p]+1;
		dfs1(to,p);
		if(siz[to]>max_son)max_son=siz[to],son[p]=to;
		siz[p]+=siz[to];
	}
}

void dfs2(int p,int t)
{
	top[p]=t;
	if(!son[p])return;
	dfs2(son[p],t);
	for(int i=h[p];~i;i=edge[i].next)
	{
		int to=edge[i].to;
		if(to==fa[p]||to==son[p])continue;
		dfs2(to,to); 
	}
}

inline int lca(int a,int b)
{
	while(top[a]!=top[b])
	{
		if(dep[top[a]]