lca板子

#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
const int M=500010;
int read(){
    int ans=0,f=1,c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}
    return ans*f;
}
int n,q,k;
LL ans,dis[M];
LL f[M][35],vis[M],deep[M];
LL first[M],cnt;
struct node{LL to,next,w;}e[M];
void ins(LL a,LL b,LL w){e[++cnt]=(node){b,first[a],w}; first[a]=cnt;}
void insert(LL a,LL b,LL w){ins(a,b,w); ins(b,a,w);}
void dfs(LL x){
    vis[x]=1;
    for(int i=1;(1<<i)<=deep[x];i++) f[x][i]=f[f[x][i-1]][i-1];
    for(int i=first[x];i;i=e[i].next){
        int now=e[i].to;
        if(!vis[now]){
            deep[now]=deep[x]+1;
            f[now][0]=x;
            dis[now]=dis[x]+e[i].w;
            dfs(now);
        }
    }
}
int find(int x,int y){
    if(deep[x]<deep[y]) swap(x,y);
    int d=deep[x]-deep[y];
    for(int i=0;(1<<i)<=d;i++) if((1<<i)&d) x=f[x][i];
    if(x==y) return x;
    for(int i=30;i>=0;i--)
     if((1<<i)<=deep[x]&&f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    return f[x][0];
}
int main(){
    int x,y,w;
    n=read();
    for(int i=1;i<n;i++) x=read(),y=read(),w=read(),insert(x,y,w);
    dfs(1);
    q=read(); k=read();
    for(int i=1;i<=q;i++){
        x=read(); y=read();
        ans=0;
        int s1=find(x,k),s2=find(y,k);
        LL sum1=dis[x]+dis[k]-dis[s1]*2;
        LL sum2=dis[y]+dis[k]-dis[s2]*2;
        ans=ans+sum1+sum2;
        printf("%lld
",ans);
    }
    return 0;
}