https://acm.uestc.edu.cn/problem/tun-tu-liang/description
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int INF = 0x3f3f3f3f; const ll mod = 1e9+7; const int maxn = 1e5+9; int a[maxn]; struct rt{ int v,next,c; }edge[maxn*2]; int head[maxn]; int tot,cnt=0; int f[maxn],d[maxn],Size[maxn],son[maxn],rk[maxn],top[maxn],id[maxn]; void add(int u,int v,int c){ edge[tot].v=v; edge[tot].c=c; edge[tot].next=head[u]; head[u]=tot++; } void dfs1(int u,int fa,int depth){ f[u]=fa; d[u]=depth; Size[u]=1; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].v; if(v==fa)continue; dfs1(v,u,depth+1); Size[u]+=Size[v]; if(Size[v]>Size[son[u]])son[u]=v; } } void dfs2(int u,int t){ top[u]=t; id[u]=++cnt; rk[cnt]=u; if(!son[u])return; dfs2(son[u],t); for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].v; if(v!=son[u]&&v!=f[u]){ dfs2(v,v); } } for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].v; if(v==f[u])continue; a[id[v]]=edge[i].c; } } int dat[maxn*4]; void pushUp(int k){ dat[k]=min(dat[k<<1],dat[k<<1|1]); } void build(int l,int r,int k){ // cout<<555<<endl; if(l==r){ dat[k]=a[l];return; } int mid=(l+r)>>1; build(l,mid,k<<1); build(mid+1,r,k<<1|1); pushUp(k); } int query(int a,int b,int l,int r,int k){ if(a<=l&&r<=b)return dat[k]; int ans=INF; int mid=(l+r)>>1; if(a<=mid)ans=min(ans,query(a,b,l,mid,k<<1)); if(b>mid)ans=min(ans,query(a,b,mid+1,r,k<<1|1)); return ans; } int Min(int x,int y){ int ans=INF,fx=top[x],fy=top[y]; // cout<<"**"<<fx<<" "<<fy<<endl; while(fx!=fy){ if(d[fx]>=d[fy]){ ans=min(ans,query(id[fx],id[x],1,cnt,1)); // cout<<query((id[fx]==id[x]?id[x]:id[fx]+1),id[x],1,cnt,1)<<endl; x=f[fx],fx=top[x]; // cout<<x<<" "<<fx<<endl; } else{ ans=min(ans,query(id[fy],id[y],1,cnt,1)); // cout<<query((id[fy]==id[y]?id[y]:id[fy]+1),id[y],1,cnt,1)<<endl; y=f[fy],fy=top[y]; // cout<<y<<" "<<fy<<endl; } } if(id[x]<id[y]){ ans=min(ans,query(id[x]+1,id[y],1,cnt,1)); } else if(id[x]>id[y]){ ans=min(ans,query(id[y]+1,id[x],1,cnt,1)); } return ans; } int main(){ ios::sync_with_stdio(false); int n,m;cin>>n>>m; int u,v,c; for(int i=0;i<=n;i++)head[i]=-1; tot=0; for(int i=0;i<n-1;i++){ cin>>u>>v>>c; add(u,v,c); add(v,u,c); } dfs1(1,0,1); dfs2(1,1); a[1]=INF; build(1,cnt,1); for(int i=0;i<m;i++){ cin>>u>>v; cout<<Min(u,v)<<endl; } return 0; } /** 15 1000 1 2 1 1 3 2 2 4 3 2 5 4 3 6 5 3 7 6 4 8 7 4 9 8 5 10 9 5 11 10 6 12 11 6 13 12 7 14 13 7 15 14 13 15 **/
