2021上海 H-Life is a Game(Kruscal重构树+树上倍增)
Published:
题目
有一个n个点m条边的无向连通图，每个点有一个权值，每条边之间也有一条边权。对于一个点，假如要走过这个点相连的某一条边，那么要保证我当前手里的权值和大于等于这条边的边权。
现在有q次询问，每次询问给出一个起始点和起始权值，每第一次经过一个点就可以获取其点权，求最多能达到的权值和。
解法
首先对于点和点之间，假如有好多种走法，我们一定是选择最短的走法，那么我们就可以先构建出这个图的最小生成树，这样能省去很多不必要的边。对于题目询问的这种问题，我们很容易猜想到要使用重构的方法去构造一棵新的树(因为一般题目里出现俩点之间最大边权等等类似的字眼，要想到kruscal重构树)。 对样例一进行kruscal重构可以得到如下图：
于是对于此题我们可以先想到一种暴力的解法，每次查询我都在树上暴力找，能往上走的话，就把子树的权值和加上，直到走不到为止。但是假如整个图是一条链的话时间复杂度就会退化到O(n^2)
考虑如何优化这个过程呢？这里很巧妙的通过一步做差+倍增使时间复杂度降了下来。那这里的做差指的是什么，又怎么倍增。
我们换个角度来考虑计算答案的贡献，以样例一的重构之后的树为例，1号点想要走到11号点的话，所需要的初始权值就是7-3=4，这里的7我们就可以理解为一个限制值，那我想从1号点走到12号点的话，所需要的初始权值是多少呢？答案是7，为什么呢？因为对于11这棵子树，所能获取的权值和是4，而我12号点的限制值是11，那么倒推回初始需要的权值就是11-4=7。通过这一步我们将问题化为了统一，因为我们只需要求出来对于我x这个点，拥有初始权值y，走到哪一格所需要的权值刚好小于等于y时，这就是我需要的答案。
这个可以通过倍增来优化时间复杂度，在倍增的同时记录一个cost[i][j]代表从i点走到其2^j的祖先点所需要的权值和为多少。 转移方程 cost[i][j]=max(cost[i][j-1],cost[f[i][j-1]][j-1]),这里取max的原因是假如连2^(j-1)都跳不到，更何况2^j，换句话说，一个点跳到2^(j-1)的贡献可能是x，2^(j-1)跳到其下一个倍增点的贡献是y，我必须先走到2^(j-1)才能走到2^(j)，那么我所需要的贡献就是这俩的max。
由于是第一次先kruscal重构树，所有东西都是第一次学，代码凑合看看。(2022.3.31)
#include<bits/stdc++.h>
#define ll long long
#define int long long
#define INF 0x3f3f3f3f
#define rep(j, a, b) for(int i=a;i<=b;i++)
#define per(j, a, b) for(int i=a;i>=b;i--)
using namespace std;
const int maxn=2e5+5;
const ll mod=1e9+7;
inline ll read(){ ll f = 1; ll x = 0;char ch = getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch = getchar();}while(ch>='0'&&ch<='9') x = (x<<3) + (x<<1) + ch - '0', ch = getchar();return x*f; }
inline ll qpow(ll a,ll b,ll MOD=mod){ll res=1;a%=MOD;while(b>0){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}return res;}
int fa[maxn],val[maxn],f[maxn][22],cost[maxn][22],lim[maxn];
struct node{
int u,v,w;
}edg[maxn<<1];
vector<int>g[maxn];
int n,m,cnt,q;
int find(int x){
if(x == fa[x]) return x;
return fa[x] = find(fa[x]);
}
bool cmp(node a,node b){ return a.w<b.w; }
void ex_kruskal(){
cnt=n;
int tot=0;
rep(i,1,2*n) fa[i]=i;
sort(edg+1,edg+1+m,cmp);
for(int i=1;i<=m;i++)
{
int a=find(edg[i].u),b=find(edg[i].v),w=edg[i].w;
if(a!=b)
{
cnt++;
val[cnt]=val[a]+val[b];
fa[b]=cnt;
fa[a]=cnt;
g[cnt].push_back(a);
g[cnt].push_back(b);
lim[cnt]=w;
tot++;
}
if(tot==n-1) break;
}
}
void dfs(int u,int father)
{
f[u][0]=father;
if(u==cnt) cost[u][0]=0x3f3f3f3f3f3f3f3f;
else cost[u][0]=lim[father]-val[u];
rep(i,1,21)
{
f[u][i]=f[f[u][i-1]][i-1];
cost[u][i]=max(cost[u][i-1],cost[f[u][i-1]][i-1]);//假如连2^(i-1)都跳不到，更何况2^(i-1)的father，这一步可以保证一直倒推回到初始所需的硬币数
}
for(auto v:g[u]){
if(v==father) continue;
dfs(v,u);
}
}
signed main()
{
n=read(),m=read(),q=read();
rep(i,1,n){
val[i]=read();
}
rep(i,1,m)
edg[i].u=read(),edg[i].v=read(),edg[i].w=read();
ex_kruskal();
//思路，将限制值和子树的硬币值做差，初始有y个硬币，通过倍增寻找分界点
dfs(cnt,0);
rep(i,1,q)
{
int x=read(),y=read();
for(int j=20;j>=0;j--)//倍增，从大到小跳
if(cost[x][j]<=y)
x=f[x][j];
printf("%lld\n",val[x]+y);
}
}