LCA+树状数组

一个LCA板子有个地方打错了，然后WA了一天😭😭😭，检查代码就是没去仔细检查板子。

> 题目链接 ：POJ 2763 Housewife Wind

题意：给一棵树。询问操作：当前节点s走到节点u所需最短距离。修改操作：改变输入的第i条边的权值

如果不加修改，拿这就是一个裸LCA的题，$dis[i]$表示根节点到$i$节点的距离，询问$a,b$ 的距离就是$dis[a]+dis[b]-2 * dis[lca(a,b)]$ ,增加修改怎么考虑呢？

可以发现改变$a->b$ (假设$b$的深度大于 $a$)的权值会影响根节点到$b$以及$b$的整个子树的距离，即改变$dis[b]和dis[b{\text{的子树中的节点}} ]$ ,改变子树可以转化为$DFS$序上的区间修改。我们不可能暴力的对区间经行修改。我们可以用树状数组完成区间修改，树状数组维护一个差分数组表示$dis$数组的变化，这个差分数组前 $i$ 项求和代表历史上的修改对第 $i$ 个位置带来的影响(即$dis$数组的变化)。

最后答案就是 $dis[u]+sum(u)+dis[s]+sum(s)-2 * (dis[lca(u,s)]+sum(lca(u,s)))$

#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<string>
#include<bitset>
#include<cmath>
using namespace std;
const int N = 1e6 + 100;
const int up = 20;
#define lowbit(x) (x&(-x))
typedef long long ll;
struct Edge{
	int to, w, next;
}edge[N];
int head[N], tot,in[N],out[N],fat[N][22],dep[N],dis[N],top;
int n, q, s,c[N],we[N];
void addedge(int from, int to, int w)
{
	edge[++tot].to = to;
	edge[tot].w = w;
	edge[tot].next = head[from];
	head[from] = tot;
}
void dfs(int u)
{
	in[u] = ++top;
	for (int i = head[u]; i != -1; i = edge[i].next)
	{
		int v = edge[i].to, w = edge[i].w;
		if (dep[v]) continue;
		dep[v] = dep[u] + 1;
		dis[v] = dis[u] + w;
		fat[v][0] = u;
		dfs(v);
	}
	out[u] = ++top;
}
void dp()
{
	for (int j = 1; j <= up; j++)
	{
		for (int i = 1; i <= n; i++)
		{
			fat[i][j] = fat[fat[i][j - 1]][j - 1];
		}
	}
}
int lca(int u, int v)
{
	if (dep[u] < dep[v]) swap(u, v);
	for (int j = up; j >= 0; j--)
	{
		if ((dep[u] - dep[v]) >> j & 1) u = fat[u][j];
	}
	if (u == v) return v;
	for (int j = up; j >= 0; j--)
	{
		if (fat[u][j] != fat[v][j]){
			u = fat[u][j];
			v = fat[v][j];
		}
	}
	return fat[u][0];
}
void add(int x,int val)
{
	while (x <= top)
	{
		c[x] += val;
		x += lowbit(x);
	}
}
int ask(int x)
{
	int res = 0;
	while (x)
	{
		res += c[x];
		x -= lowbit(x);
	}
	return res;
}
int main()
{
	memset(head, -1, sizeof(head));
	scanf("%d%d%d", &n, &q, &s);
	for (int i = 1; i < n ; i++)
	{
		int u, v;
		scanf("%d%d%d", &u, &v, &we[i]);
		addedge(u, v, we[i]);
		addedge(v, u, we[i]);
	}
	dep[1] = 1;
	fat[1][0] = 1;
	dfs(1);
	dp();
	for (int i = 0; i < q; i++)
	{
		int op, x, y;
		scanf("%d", &op);
		if (op == 0){
			scanf("%d", &x);
			int Lca = lca(x, s);
			printf("%d\n", dis[s] + dis[x] + ask(in[x]) + ask(in[s]) - 2 * (dis[Lca] + ask(in[Lca])));
			s = x;
		} 
		else
		{
			scanf("%d%d", &x, &y);
			int u = edge[2*(x-1)+1].to, v = edge[x << 1].to;
			if (dep[u] < dep[v]) swap(u, v);
			add(in[u], y - we[x]);
			add(out[u] + 1, we[x] - y);
			we[x] = y;
		}
	}
    return 0;
}

我们也可以不适用dis数组。

for (int i = 1; i < n; i++)
{
    scanf("%d%d%d", &a[i], &b[i], &we[i]);
    addedge(a[i], b[i], we[i]);
    addedge(b[i], a[i], we[i]);
}
for (int i = 1; i < n; i++)
{
    if (dep[a[i]] < dep[b[i]]) swap(a[i], b[i]);
    add(in[a[i]], we[i]);//直接插入,这也可以理解为和修改操作一样，不断修改边权的过程。
    add(out[a[i]] + 1, -we[i]);
}

printf("%d\n", ask(in[x]) + ask(in[s]) - 2 * (ask(in[Lca])));