int dep[N]={};int dis[N]={};int f[N][30]={};void dfs(int u,int fat){	f[u][0]=fat;	for(int i=1;i<=20;i++)f[u][i]=f[f[u][i-1]][i-1];	for(int i=first[u];i;i=e[i].nxt){		int v=e[i].v;		if(v!=fat){			dis[v]=dis[u]+e[i].w;			dep[v]=dep[u]+1;			dfs(v,u);		}	}}int LCA(int x,int y){	if(dep[x]
    
     =0;i--){		if(dep[x]-(1<
     
      =dep[y]){			x=f[x][i];		}	}	if(x==y)return x;	for(int i=20;i>=0;i--){		if(f[x][i]!=f[y][i]){			x=f[x][i];			y=f[y][i];		}	}	return f[x][0];}