题目大意：
给定n个点，m条边，有q个询问
每个点有一个（能量值）点权，每条边有一个边权
m条边描述为u v w表示有一条u与v相连的边权为w的通路
在每一次询问中，给定一个点x和现有的能量值k，每次只能是在当前能量值大于边权的时候到达另一个点，并获取这个点的能量值（路可以重复走），问最终能够获得多大的能量值
思路：
克鲁斯卡尔重构树
在建立克鲁斯卡尔重构树的时候，会将边权化为点权来处理并建立成一个堆，而且原先的节点一定是重构树中的 叶子节点 ，除了叶子节点之外的其他点都是原先的边权
在克鲁斯卡尔重构树中，从叶子节点以上到根的路径中，点权一定是单调不减的
所以说给定的节点要是能够直接跳到祖先节点的话，那么说以这个节点为根的子树都能够访问到
所以说在这里可以使用倍增来处理，并且在维护以某节点为根的子树的所有节点的能量值
这样如果说能够跳过去的话，就将能量值的贡献加过去，直到不能跳为止
code：
ll fa[maxn],siz[maxn],a[maxn]; vector<int> gra[maxn]; ll bz[27][maxn],n,m,cnt,q; struct node { int u,v,w; friend bool operator<(node a,node b) { return a.w < b.w; } node() { } node(int _u,int _v,int _w) { u = _u,v = _v,w = _w; } }; vector<node> vet; int get(int x) { if(x == fa[x]) return x; else return fa[x] = get(fa[x]); } void init() { for(int i=0; i<=n*2; i++) fa[i] = i;//,siz[i] = 1; } void kru() { sort(vet.begin(),vet.end()); for(int i=0; i<m; i++) { node nd = vet[i]; int u = nd.u,v = nd.v,w = nd.w; int fau = get(u); int fav = get(v); if(fau != fav) { a[++cnt] = w; fa[cnt] = fa[fau] = fa[fav] = cnt; gra[fau].push_back(cnt); gra[cnt].push_back(fau); gra[fav].push_back(cnt); gra[cnt].push_back(fav); } } } void dfs(int u,int fa) { bz[0][u] = fa; for(int i=1; i<=20; i++) { bz[i][u] = bz[i-1][bz[i-1][u]]; } for(int to:gra[u]) { if(to == fa) continue; dfs(to,u); siz[u] += siz[to]; } } int main() { n = read,m = read,q = read; init(); cnt = n; for(int i=1; i<=n; i++) siz[i] = read; for(int i=1; i<=m; i++) { int u = read,v = read,w = read; vet.push_back(node {u,v,w}); } kru(); dfs(cnt,0); a[0] = ((1LL<<31)-1); for(int i=1; i<=q; i++) { ll u = read,s = read; ll now = s + siz[u]; while(u != cnt) { int tu = u; for(int i=20; i>=0; i--) { if(a[bz[i][u]] <= now) u = bz[i][u]; } if(tu == u) break; now = siz[u] + s; } // printf("->>>> %lld\n",now); printf("%lld\n",now); } return 0; } /** **/
![[HDU 7136] Jumping Monkey | 并查集 | 逆向思维](https://ucc.alicdn.com/pic/developer-ecology/0986dbf7ae7b4caf842656dfc21105d2.png?x-oss-process=image/resize,h_160,m_lfit)
