Hdu 2586 树链剖分求LCA

Code:

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=40000+3;
typedef long long ll;
ll dis[maxn];
int son[maxn],siz[maxn],rank1[maxn],p[maxn],top[maxn];
struct Edge {
	int from, to, dis;
	Edge(int from, int to, int dis) :from(from), to(to), dis(dis){}
};
struct LCA{
	vector<Edge>edges;
	vector<int>G[maxn];
	void init(int n){
		for(int i=1;i<=n;++i)G[i].clear();
		edges.clear();
		memset(son,-1,sizeof(son));memset(dis,0,sizeof(dis));
		memset(rank1,0,sizeof(rank1));memset(p,0,sizeof(p));
		memset(siz,0,sizeof(siz));memset(top,0,sizeof(top));
	}
	void add_edge(int from,int to,int dis){
		edges.push_back(Edge(from,to,dis));
		int m=edges.size()-1;
		G[from].push_back(m);
	}
	void dfs1(int u,int fa,int cur,ll dep)
	{
		siz[u]=1,p[u]=fa,rank1[u]=cur;
        dis[u]=dep;
        for(int i=0;i<G[u].size();++i)
        {
        	int m=G[u][i];
        	Edge E=edges[m];
        	if(E.to!=fa)
        	{
	        	dfs1(E.to,u,cur+1,dep+E.dis);
	        	siz[u]+=siz[E.to];
	        	if(son[u]==-1||siz[son[u]]<siz[E.to])son[u]=E.to;
	        }
        }
	}
	void dfs2(int u,int tp){
		top[u]=tp;
		if(son[u]!=-1)dfs2(son[u],tp);
		for(int i=0;i<G[u].size();++i)
		{
			int m=G[u][i];
			Edge E=edges[m];
			if(E.to!=p[u]&&E.to!=son[u])dfs2(E.to,E.to);
		}
	}
	int query(int x,int y)
	{
		while(top[x]!=top[y])
		{
			if(rank1[top[x]]<=rank1[top[y]])y=p[top[y]];
			else x=p[top[x]];
		}
		if(rank1[x]<=rank1[y])return x;
		return y;
	}
	ll ans(int x,int y)
	{
		ll m1=dis[x],m2=dis[y];
		int lca=query(x,y);
		return m1+m2-2*dis[lca];
	}
};
int main(){
	int T;scanf("%d",&T);
    while(T--)
    {
    	int n,m;scanf("%d%d",&n,&m);
    	LCA _lca;
    	_lca.init(n);
		for(int i=1;i<n;++i)
		{
		   int from,to,dis;
		   scanf("%d%d%d",&from,&to,&dis);
		   _lca.add_edge(from,to,dis);
		   _lca.add_edge(to,from,dis);
		}    	
		_lca.dfs1(1,-1,1,0);
		_lca.dfs2(1,1);
		for(int i=1;i<=m;++i)
		{
			int a,b;scanf("%d%d",&a,&b);
			printf("%lld
",_lca.ans(a,b));
		}
    }
    return 0;
}