这个题目和lca类似，就是要计算两个点间所有点的最大权值点。
可以在更新祖先的时候更新最大值。
（记得多组输入
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <string> #include <vector> #include <map> #include <set> #include <queue> #include <list> #include <cstdlib> #include <iterator> #include <cmath> #include <iomanip> #include <bitset> #include <cctype> using namespace std; #define lson (l , mid , rt << 1) #define rson (mid + 1 , r , rt << 1 | 1) #define debug(x) cerr << #x << " = " << x << " "; #define pb push_back #define pq priority_queue #pragma comment(linker, "/STACK:10240000000,10240000000")//扩栈，要用c++交，用g++交并没有什么卵用。。 typedef long long ll; typedef unsigned long long ull; typedef pair<ll ,ll > pll; typedef pair<int ,int > pii; #define fi first #define se second #define OKC ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define FT(A,B,C) for(int A=B;A <= C;++A) //用来压行 #define REP(i , j , k) for(int i = j ; i < k ; ++i) const ll mos = 0x7FFFFFFF; //2147483647 const ll nmos = 0x80000000; //-2147483648 template<typename T> inline T read(T&x){ x=0;int f=0;char ch=getchar(); while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x=f?-x:x; } // #define _DEBUG; //*// #ifdef _DEBUG freopen("input", "r", stdin); // freopen("output.txt", "w", stdout); #endif ///*-----------------show time----------------*/ const int maxn = 20009; vector<int>mp[maxn]; int n,m; int anc[maxn][30]; int maxv[maxn][30],a[maxn]; int fa[maxn]; int deep[maxn]; void dfs(int x){ anc[x][0] = fa[x]; maxv[x][0] = max(a[fa[x]],a[x]); for(int i=1; i<=22; i++){ anc[x][i] = anc[anc[x][i-1]][i-1]; maxv[x][i] = max( maxv[x][i-1], maxv[anc[x][i-1]][i-1]); } for(int i=0; i<mp[x].size(); i++){ int u = mp[x][i]; if(u==fa[x])continue; fa[u] = x; deep[u] = deep[x] + 1; dfs(u); } } int main(){ while(~scanf("%d%d", &n, &m)){ for(int i=1; i<=n; i++)mp[i].clear(); memset(deep,0,sizeof(deep)); memset(fa,-1,sizeof(fa)); memset(anc,0,sizeof(anc)); memset(maxv, 0, sizeof(maxv)); for(int i=1; i<n; i++){ int u,v; scanf("%d%d", &u, &v); mp[u].pb(v); mp[v].pb(u); } for(int i=1; i<=n; i++){ scanf("%d", &a[i]); } fa[1] = 0; deep[1] = 1; dfs(1); for(int i=1; i<=m; i++){ int u,v; scanf("%d%d", &u, &v); if(u==v){ printf("%d ",a[u]); continue; } if(deep[u] >= deep[v]){ swap(u,v); } int mx = max(a[v] , a[u]); for(int j=22; j>=0; j--){ if(deep[u] <= deep[anc[v][j]]) { mx = max(mx,maxv[v][j]); v = anc[v][j]; } } if(u==v){ printf("%d ",mx); } else printf("-1 "); } } return 0; }