树的相交路径(daan)

zhangyihao 2022-02-26 20:18:38 0
#include<bits/stdc++.h>
using namespace std;
const int maxn=300005;
int n,m,a,b,c,d,np=0,op;
int first[maxn],dist[maxn],fa[maxn][20],dep[maxn],st[10];
struct edge
{
	int next,to,w;
}E[maxn<<1];
void add(int u,int v,int w)
{
	E[++np]=(edge){first[u],v,w};
	first[u]=np;
}
void DFS(int i,int f,int d,int de)
{
	dist[i]=d;
	fa[i][0]=f;
	dep[i]=de;
	for(int j=1;j<=18;j++)
	   fa[i][j]=fa[fa[i][j-1]][j-1];
	for(int p=first[i];p;p=E[p].next)
		if(E[p].to!=f)
		DFS(E[p].to,i,d+E[p].w,de+1);	  
}
int LCA(int x,int y)
{
	if(dep[x]<dep[y])swap(x,y);
	int delta=dep[x]-dep[y],j=0,z;
	while(delta)
	{
		if(delta&1)x=fa[x][j];
		delta>>=1;
		j++; 
	}
	if(x==y) return x;
	 	    
    for(j=18;j>=0;j--)
	if(fa[x][j]!=fa[y][j])x=fa[x][j],y=fa[y][j];
	
	return z=fa[x][0];
}
int len(int a,int b)
{
	return dist[a]+dist[b]-2*dist[LCA(a,b)];
}
bool solve1(int a,int b,int c,int d)
{
	int ab=len(a,b),cd=len(c,d);
	if(len(c,a)+ab+len(b,d)==cd || len(c,b)+ab+len(a,d)==cd)
	  return 1;
	else 
	  return 0;
}
void solve2(int a,int b,int c,int d)
{
	st[0]=LCA(a,b);
	st[1]=LCA(a,c);
	st[2]=LCA(a,d);
	st[3]=LCA(b,c);
	st[4]=LCA(b,d);
	st[5]=LCA(c,d);
	sort(st,st+6);
	int tot=unique(st,st+6)-st;
	int maxv=0;
	for(int i=0;i<tot;i++)
	 for(int j=i+1;j<tot;j++)
		if(solve1(st[i],st[j],a,b) && solve1(st[i],st[j],c,d) )
		  maxv=max(maxv,len(st[i],st[j]));
    printf("%d\n",maxv);
}
int main()
{
	int u,v,t;
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++)
	{
		scanf("%d%d%d",&u,&v,&t);
		add(u,v,t);
		add(v,u,t);
	}
	DFS(1,0,0,1);
	while(m--)
	{
		scanf("%d%d%d%d%d",&op,&a,&b,&c,&d);	
		if(op==1) 
		   if(solve1(a,b,c,d))
		      printf("Yes\n"); 
		   else printf("No\n");
		else solve2(a,b,c,d);
	}
	return 0;
}
{{ vote && vote.total.up }}