H题 Life is a Game 题解
重构树 第一次听说 就是最小生成树但是每次加上一个虚拟的点 点的权重是两点相连的边权 然后从边权越大的点在更上面 所以如果我可以到达一个点我就一定可以到达他下面的所有点并且获得下面所有点的权重（经验） 怎么判断我从一个点出发能不能到达呢 我先预处理从每一个点出发到达他的所有祖先要的阈值是多少 然后拿题目给的k判断大于阈值就能到小于就不行
然后他的跳跃是二进制的跳跃 所以不会有太多层logn层
include
include
include
using namespace std;
const int maxN = 2e5 + 7;
struct Edge {
int from, to, dis;
}e[maxN], initEdge[maxN];
int n, m, q, head[maxN], cnt, tot, fa[maxN], f[maxN][23];
long long sum[maxN], maxNum[maxN][23], val[maxN];
inline void add(int u, int v, int w = 0)
{
e[++cnt].from = head[u];
e[cnt].to = v;
e[cnt].dis = w;
head[u] = cnt;
}
bool cmp(Edge x, Edge y)
{
return x.dis < y.dis;
}
int Find(int x)
{
return fa[x] == x? x : fa[x] = Find(fa[x]);
}
inline void KruskalTree() //Kruskal重构树
{
sort(initEdge + 1, initEdge + 1 + m, cmp);//先按边权排个序 小的在前
for(int i = 1; i <= n; ++i)//初始化
fa[i] = i;
tot = n;
for(int i = 1; i <= m; ++i) {
if(tot == (n << 1) - 1)
break;
int fx = Find(initEdge[i].from), fy = Find(initEdge[i].to);
if(fx == fy)
continue;
val[++tot] = initEdge[i].dis;
fa[tot] = fa[fx] = fa[fy] = tot;
add(tot, fx); add(tot, fy);
}
}
void dfs1(int x) //记录祖先,计算sum数组
{
if(x <= n) {
sum[x] = val[x];
return ;
}
for(int i = head[x]; i; i = e[i].from) {
int y = e[i].to;
f[y][0] = x;
dfs1(y);
sum[x] += sum[y];
}
}
void dfs2(int x) //更新maxNum （阈值）
{
maxNum[x][0] = val[f[x][0]] - sum[x];
for(int i = 1; i <= 19; ++i) {
f[x][i] = f[f[x][i - 1]][i - 1];
maxNum[x][i] = max(maxNum[x][i - 1], maxNum[f[x][i - 1]][i - 1]);
}
for(int i = head[x]; i; i = e[i].from) {
int y = e[i].to;
dfs2(y);
}
}
inline int query(int x, int k) //倍增求结果
{
for(int i = 19; i >= 0; --i)
if(f[x][i] && maxNum[x][i] <= k)//找到最大一个可以跳到的祖先然后再继续跳
x = f[x][i];
return sum[x];
}
int main()
{
scanf("%d%d%d", &n, &m, &q);
for(int i = 1; i <= n; ++i)
scanf("%lld", &val[i]);
for(int i = 1; i <= m; ++i)
scanf("%d%d%d", &initEdge[i].from, &initEdge[i].to, &initEdge[i].dis);//到的点
KruskalTree();
dfs1(tot); dfs2(tot); //注意,tot节点是新树的根节点
for(int i = 1; i <= q; ++i) {
int x, y;
scanf("%d%d", &x, &y);
printf("%d\n", y + query(x, y));
}
return 0;
}