MENU

POJ 2763 Housewife Wind

2019-07-01 • 阅读: 21 • 图论—LCA数据结构—树状数组阅读设置

LCA+树状数组

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

> 题目链接 :POJ 2763 Housewife Wind

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

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

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

最后答案就是 dis[u]+sum(u)+dis[s]+sum(s)2(dis[lca(u,s)]+sum(lca(u,s)))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])));

返回文章列表 文章二维码 打赏
本页链接的二维码
打赏二维码