我不知道题解应该叫什么名字

· · 题解

处理每一个节点的复苏情况是简单的。

因此我们可以使用倍增数组实现一个数组 dea[x][i]，代表从 x 开始复苏 2^i 次可到达的地方。

因此，我们可以使用 \log 的复杂度实现任意的移动。

对于每一次查询，我们如下考虑：

最简单的方法肯定是从 s 到 lca(s,t) 再到 t，然而我们发现到达 lca(s,t) 时的生命是不能够直接求出的。

因此，我们考虑移动到 s 和 t 刚刚好最后一次复苏的位置。

也就是说，我们定义 s' 代表 s 到 lca(s,t) 最后一次复苏后的位置，定义 t' 代表 t 到 lca(s,t) 最后一次复苏后的位置。

那么，我们要处理的代价为 dis(s,s')+dis(t,t')+dis(s',t')。

前两个已经可以使用刚才的倍增解决了，所以我们只需要思考如何处理 dis(s',t')。

因为两端都已经不足 k 了，所以代价只有可能是 0 或 1，那么我们就只需要思考是否需要复苏——我们直接用树上前缀和就可以得到是否需要复苏了。

以下是代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=2e5+5,M=4e5+5;
int ver[M],ne[M],w[M],head[N],tot;
int lc[N][30],dea[N][30],dep[N],sum[N];
int n,k;

inline int read(){
    int s=0;char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return s;
}

inline void add(int x,int y,int z){
    ver[++tot]=y,w[tot]=z;
    ne[tot]=head[x],head[x]=tot;
}

inline int get(int x){//x复苏一次能到达的位置 
    int tmp=x;
    for(int i=20;i>=0;i--) if(sum[x]-sum[lc[tmp][i]]<k) tmp=lc[tmp][i];//还可以跳就往上跳
    return lc[tmp][0];//跳上去后复苏 
}

inline void dfs(int x,int fa){
    dep[x]=dep[fa]+1,lc[x][0]=fa;
    for(int i=1;i<=20;i++) lc[x][i]=lc[lc[x][i-1]][i-1];
    dea[x][0]=get(x);
    for(int i=1;i<=20;i++) dea[x][i]=dea[dea[x][i-1]][i-1];
    for(int i=head[x];i;i=ne[i]){
        int y=ver[i];
        if(y==fa) continue;
        sum[y]=sum[x]+w[i];
        dfs(y,x);
    } 
}

inline int lca(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=20;i>=0;i--) 
        if(dep[lc[x][i]]>=dep[y]) x=lc[x][i];
    if(x==y) return x;
    for(int i=20;i>=0;i--)
        if(lc[x][i]!=lc[y][i]) x=lc[x][i],y=lc[y][i];
    return lc[x][0]; 
}

signed main(){
    cin>>n>>k;
    for(int i=1;i<n;i++){
        int x=read(),y=read(),z=read();
        add(x,y,z);add(y,x,z);
    }
    dfs(1,0);
    int T;cin>>T;
    while(T--){
        int x=read(),y=read();
        int z=lca(x,y);
        int ans=0;
        for(int i=20;i>=0;i--)
            if(dep[dea[x][i]]>=dep[z]) x=dea[x][i],ans+=(1<<i);//x 跳上去 
        for(int i=20;i>=0;i--)
            if(dep[dea[y][i]]>=dep[z]) y=dea[y][i],ans+=(1<<i);//y 跳上去
        cout<<ans+((sum[x]+sum[y]-2*sum[z]>=k)?1:0)<<"\n";//两端不会再有，所以只需要检查中间是否需要 
    }
    return 0;
}