T1 第零题

---

神秘结论：从一个点满体力到另一个点的复活次数与倒过来相同。

于是预处理出每个点向上走第$2^i$个死亡点的位置，具体实现可以倍增或二分。

每次询问先从两个点同时向上倍增，都转到离$LCA$最近的死亡点上，然后判断，如果现在两点路径上权值大于$k$则答案加$1$。

$code:$

 1 #include<bits/stdc++.h>
 2 #define int long long
 3 using namespace std;
 4 
 5 namespace IO{
 6     inline int read(){
 7         char ch=getchar(); int x=0,f=1;
 8         while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }
 9         while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
10         return x*f;
11     }
12     inline void write(int x,char sp){
13         char ch[20]; int len=0;
14         if(x<0){ putchar('-'); x=~x+1; }
15         do{ ch[len++]=x%10+(1<<4)+(1<<5); x/=10; }while(x);
16         for(int i=len-1;~i;--i) putchar(ch[i]); putchar(sp);
17     }
18     inline int max(int x,int y){ return x<y?y:x; }
19     inline int min(int x,int y){ return x<y?x:y; }
20     inline void swap(int &x,int &y){ x^=y^=x^=y; }
21     inline void chmax(int &x,int y){ x=x<y?y:x; }
22     inline void chmin(int &x,int y){ x=x<y?x:y; }
23 } using namespace IO;
24 
25 const int NN=2e5+5;
26 int n,q,k,s,t,idx,to[NN<<1],nex[NN<<1],w[NN<<1],head[NN],det[NN][20],mi[20];
27 inline void add(int a,int b,int c){
28     to[++idx]=a; nex[idx]=head[b]; head[b]=idx; w[idx]=c;
29     to[++idx]=b; nex[idx]=head[a]; head[a]=idx; w[idx]=c;
30 }
31 
32 namespace Tree_divide{
33     int cnt,fa[NN],dfn[NN],dep[NN],id[NN],top[NN],siz[NN],son[NN],pre[NN];
34     void dfs1(int s,int f){
35         dep[s]=dep[f]+1; siz[s]=1; fa[s]=f;
36         for(int i=head[s];i;i=nex[i]){
37             int v=to[i];
38             if(v==f) continue;
39             pre[v]=pre[s]+w[i];
40             dfs1(v,s);
41             siz[s]+=siz[v];
42             if(siz[v]>siz[son[s]]) son[s]=v;
43         }
44     }
45     void dfs2(int s,int t){
46         top[s]=t; dfn[s]=++cnt; id[cnt]=s;
47         if(!son[s]) return;
48         dfs2(son[s],t);
49         for(int i=head[s];i;i=nex[i]){
50             int v=to[i];
51             if(v!=fa[s]&&v!=son[s]) dfs2(v,v);
52         }
53     }
54     inline int LCA(int x,int y){
55         while(top[x]!=top[y])
56             if(dep[top[x]]>dep[top[y]]) x=fa[top[x]];
57             else y=fa[top[y]];
58         return dep[x]<dep[y]?x:y;
59     }
60     inline int get(int x){
61         int tmp=pre[x],l,r,res;
62         while(x&&tmp-pre[top[x]]<k) x=fa[top[x]];
63         if(!x) return 0;
64         r=dfn[x]; l=dfn[top[x]];
65         while(l<=r){
66             int mid=l+r>>1;
67             if(tmp-pre[id[mid]]>=k) l=mid+1, res=mid;
68             else r=mid-1;
69         }
70         return id[res];
71     }
72     void dfs3(int s){
73         det[s][0]=get(s);
74         for(int i=1;i<20;i++) det[s][i]=det[det[s][i-1]][i-1];
75         for(int i=head[s];i;i=nex[i])
76             if(to[i]!=fa[s]) dfs3(to[i]);
77     }
78 } using namespace Tree_divide;
79 
80 signed main(){
81     n=read(); k=read(); mi[0]=1;
82     for(int i=1;i<20;i++) mi[i]=mi[i-1]*2;
83     for(int a,b,c,i=1;i<n;i++)
84         a=read(),b=read(),c=read(), add(a,b,c);
85     dfs1(1,0); dfs2(1,1); dfs3(1);
86     q=read();
87     while(q--){
88         s=read(); t=read();
89         int lca=LCA(s,t),ans=0;
90         for(int i=19;~i;i--){
91             if(dep[det[s][i]]>=dep[lca]) s=det[s][i], ans+=mi[i];
92             if(dep[det[t][i]]>=dep[lca]) t=det[t][i], ans+=mi[i];
93         }
94         if(pre[s]+pre[t]-2*pre[lca]>=k) ++ans;
95         write(ans,'\n');
96     }
97     return 0;
98 }

T1