Description
在一片苍茫的大海上，有n座岛屿，岛屿与岛屿之间由桥梁连接，所有的岛屿刚好被桥梁连接成一个树形结构，即共n−1架桥梁，且从任何一座岛屿出发都能到达其他任何一座岛屿。
第i座桥梁有一个承重量wi，表示该桥梁一次性最多通过重量为wi的货物。
现在有m个货物运输路线，第i个路线要从岛屿xi出发到达岛屿yi。为了最大化利益，你需要求出在不超过路线上任何一架桥梁的承重量的基础上，每个路线最多运输重量为多少货物。
Input
第一行为两个整数n,m。
接下来n−1行，每行三个整数x,y,w，表示有一座承重量为w的桥梁连接岛屿x和y。
接下来m行，每行两个整数x,y，表示有一条从岛屿x出发到达岛屿y的路线，保证x≠y。
Output
输出共m行，每行一个整数，第i个整数表示第i条路线的最大重量。
Samples
Input 复制
6 5
1 2 2
2 3 5
2 4 2
2 5 3
5 6 1
2 4
6 2
1 3
3 5
1 6
Output
2
1
2
3
1
思路：
类似于维护l c a的过程，多维护一个m i n n表示最小价值；
m i n n [ i ] [ j ]表示从i ii到第2 j个祖先的所经过的路的最小价值;
询问的时候类似于求l c a的过程，边跳边更新最小价值；
注意每次要先更新最小价值再往上跳
代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll,ll>PLL; typedef pair<int,int>PII; typedef pair<double,double>PDD; #define I_int ll inline ll read() { ll x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-')f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); } return x*f; } #define read read() #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define perr(i,a,b) for(int i=(a);i>(b);i--) ll ksm(ll a,ll b,ll p) { ll res=1; while(b) { if(b&1)res=res*a%p; a=a*a%p; b>>=1; } return res; } #define PI acos(-1) const double eps=1e-8; const int maxn=1e6+7; int h[maxn],idx; struct node{ int e,ne,w; }edge[maxn]; void add(int u,int v,int w){ edge[idx]={v,h[u],w};h[u]=idx++; } int n,m,a[maxn],res; int minn[maxn][25]; int dep[maxn],fa[maxn][25]; void dfs(int x,int f){ fa[x][0]=f; for(int i=1;i<=20;i++){ fa[x][i]=fa[fa[x][i-1]][i-1]; minn[x][i]=min(minn[x][i-1],minn[fa[x][i-1]][i-1]); } for(int i=h[x];~i;i=edge[i].ne){ int j=edge[i].e; if(j==f) continue; dep[j]=dep[x]+1; minn[j][0]=edge[i].w; dfs(j,x); } } int lca(int a,int b){ int ans=1e9; if(dep[a]<dep[b]) swap(a,b); for(int k=20;k>=0;k--) if(dep[fa[a][k]]>=dep[b]) ans=min(ans,minn[a][k]),a=fa[a][k];///使a,b跳到同一层 for(int k=20;k>=0;k--) if(fa[a][k]!=fa[b][k]){ ans=min(ans,minn[a][k]); ans=min(ans,minn[b][k]); a=fa[a][k],b=fa[b][k]; } if(a!=b) ans=min(ans,min(minn[a][0],minn[b][0])); return ans; } int main() { n=read,m=read; memset(h,-1,sizeof h); for(int i=1;i<=n-1;i++){ int u=read,v=read,w=read; add(u,v,w);add(v,u,w); } memset(minn,0x3f,sizeof minn); dfs(1,0); while(m--){ int x=read,y=read; printf("%d\n",lca(x,y)); } return 0; }
