CODEVS 2370小屋の木

テーマ説明Description
小さな機械室にはファン犬種の木があり、木にはN個のノードがあり、ノード番号は0からN-1で、2匹の虫が漂犬と大吉犬と呼ばれ、2つの異なるノードに分かれている.ある日、彼らは1つのノードに登ってベースを作りたいと思っていましたが、2匹の虫として、あまり精力を費やしたくありません.あるノードから父親ノードに登るにはcのエネルギーがかかることが知られています(父親ノードからこのノードに登るのも同じです).彼らは最も精力を費やした道を見つけて、基礎を作るときに精力を旺盛にしたいと思っています.彼らはあなたがこの道を見つけるためにプログラムを設計して、少なくともどれだけの精力を費やす必要があるかを教えてほしいと思っています.
入力記述Input Description
最初の行はnであり、次にn−1行は3つの整数u,v,cを有する.ノードuがノードvに登るのにcの労力がかかることを示す.n+1行目の整数mはm回のクエリを表す.次にm行の各行には2つの整数uがあり、vは2匹の虫がいるノードを表す
出力記述Output Description
合計m行で、各行に1つの整数があり、この質問に対して得られた最短距離を表す.
サンプル入力Sample Input
3
1 0 1
2 0 1
3
1 0
2 0
1 2
サンプル出力Sample Output
1
1
2
データ範囲とヒントData Size&Hint
1<=n<=50000, 1<=m<=75000, 0<=c<=1000
テーマは2点間の簡単な経路長、木断秒a~を要求する.
午后fftを学んで、数论は私を虐げて、感じはとても退廃的で、lctを打つことを选びました..
makeroot以降xには左の息子はなく,access y以降主splayはx->lca(x,y)->y間の情報のみを維持した.

#include
using namespace std;
#define Inc(i,L,R) for(register int i=(L);i<=(R);++i)
#define Red(j,R,L) for(register int j=(R);j>=(L);--j)
const int N = 2e5+10;
struct Inform{
	int num,sum;
}a[N]; 
struct Splay{
	bool rev[N];
	int p[N],ch[N][2];
	#define Ls(v) ch[v][0]
	#define rs(v) ch[v][1]
	bool is_root(int x){
		return (Ls(p[x])^x)&&(rs(p[x])^x);
	}
	inline void pushdown(int x){
		if(rev[x]){
			rev[Ls(x)]^=1,rev[rs(x)]^=1;
			swap(Ls(x),rs(x));
			rev[x]=0;
		}
	}
	inline void maintain(int x){
		a[x].sum=a[Ls(x)].sum+a[rs(x)].sum+a[x].num;
	}
	inline void rot(int x){
		int f=p[x],gf=p[f],type=rs(f)==x,son=ch[x][!type];
		if(!is_root(f))ch[gf][rs(gf)==f]=x;p[x]=gf;
		ch[p[son]=f][type]=son,maintain(f);
		ch[p[f]=x][!type]=f,maintain(x);
	}
	int top,stk[N];
	inline void splay(int x){
		stk[++top]=x;
		if(!is_root(x))for(int i=x;!is_root(i);i=p[i])stk[++top]=p[i];
		while(top)pushdown(stk[top--]);
		while(!is_root(x)){
			if(is_root(p[x]))return rot(x),void();
			if((rs(p[p[x]])==p[x])==(rs(p[x])==x))rot(p[x]);
			rot(x);
		}
	}
};
struct LCT{
	Splay sp;
	inline int access(int x){
		int lastx=0;
		while(x){
			sp.splay(x);
			sp.rs(x)=lastx;
			sp.maintain(x);
			lastx=x;
			x=sp.p[x];
		}
		return lastx;
	}
	inline void make_root(int x){
		access(x);
		sp.splay(x);
		sp.rev[x]^=1;
	}
	inline void Link(int x,int y){
		make_root(x),sp.p[x]=y;
	}
	inline void work(int x,int y){
		make_root(x);
		access(y);
		sp.splay(y);
		cout<