POJ3237 Tree 树链剖分 边权

时间:2022-02-03 23:46:41

POJ3237 Tree 树链剖分 边权

传送门:http://poj.org/problem?id=3237

题意:

n个点的,n-1条边

修改单边边权

将a->b的边权取反

查询a->b边权最大值

题解:

修改边权就查询点的深度大的点,用大的点去存这条边的边权,其余的就和点权的是一样的了

取反操作用线段树维护,区间最大值取反就是区间最小值,区间最小值取反就是区间最大值

所以维护两颗线段树即可,lazy标记表示覆盖单边的边权

代码:

#include <set>
#include <map>
#include <cmath>
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef unsigned long long uLL;
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define bug printf("*********\n")
#define FIN freopen("input.txt","r",stdin);
#define FON freopen("output.txt","w+",stdout);
#define IO ios::sync_with_stdio(false),cin.tie(0)
#define debug1(x) cout<<"["<<#x<<" "<<(x)<<"]\n"
#define debug2(x,y) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<"]\n"
#define debug3(x,y,z) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<" "<<#z<<" "<<z<<"]\n"
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
struct EDGE {
int v, nxt, w;
} edge[maxn << 1];
int head[maxn], tot;
void add_edge(int u, int v, int w) {
edge[tot].v = v;
edge[tot].w = w;
edge[tot].nxt = head[u];
head[u] = tot++;
}
int sz[maxn], dep[maxn], son[maxn], id[maxn], Rank[maxn], cnt, fa[maxn], top[maxn];
int d[maxn];
void dfs1(int u, int f, int cnt) {
fa[u] = f;
dep[u] = cnt;
sz[u] = 1;
son[u] = 0;
int tmp = 0;
for(int i = head[u]; i != -1; i = edge[i].nxt) {
int v = edge[i].v;
if(v != f) {
dfs1(v, u, cnt + 1);
if(tmp < sz[v]) {
son[u] = v;
tmp = sz[v];
}
sz[u] += sz[v];
} }
}
void dfs2(int u, int tp) {
top[u] = tp;
id[u] = ++cnt;
Rank[cnt] = u;
if(son[u]) dfs2(son[u], tp);
for(int i = head[u]; i != -1; i = edge[i].nxt) {
int v = edge[i].v;
if(v == fa[u]) continue;
if(v == son[u]) {
d[id[v]] = edge[i].w;
continue;
}
dfs2(v, v);
d[id[v]] = edge[i].w;
}
}
void prebuild() {
dfs1(1, 0, 0);
dfs2(1, 1);
} int Max[maxn << 2];
int Min[maxn << 2];
// int sum[maxn<<2];
int lazy[maxn]; void push_up(int rt) {
Max[rt] = max(Max[ls], Max[rs]);
Min[rt] = min(Min[ls], Min[rs]); }
void build(int l, int r, int rt) {
lazy[rt] = 1;
if(l == r) {
Max[rt] = Min[rt] = d[l];
return;
}
int mid = (l + r) >> 1;
build(lson);
build(rson);
push_up(rt);
}
void push_down(int rt) {
if(lazy[rt] == -1) {
lazy[ls] = -lazy[ls];
lazy[rs] = -lazy[rs];
lazy[rt] = 1;
swap(Max[ls], Min[ls]);
Max[ls] *= -1;
Min[ls] *= -1;
swap(Max[rs], Min[rs]);
Max[rs] *= -1;
Min[rs] *= -1;
}
}
void update_pos(int pos, int val, int l, int r, int rt) {
if(l == r) {
lazy[rt] = 1;
Max[rt] = Min[rt] = val;
return;
}
push_down(rt);
int mid = (l + r) >> 1;
if(pos <= mid) update_pos(pos, val, lson);
else update_pos(pos, val, rson);
push_up(rt);
}
void update(int L, int R, int l, int r, int rt) {
if(L <= l && r <= R) {
lazy[rt] = -lazy[rt];
swap(Max[rt], Min[rt]);
Max[rt] *= -1;
Min[rt] *= -1;
return;
}
push_down(rt);
int mid = (l + r) >> 1;
if(L <= mid) update(L, R, lson);
if(R > mid) update(L, R, rson);
push_up(rt);
}
int query(int L, int R, int l, int r, int rt) {
if(L <= l && r <= R) {
return Max[rt];
}
push_down(rt);
int mid = (l + r) >> 1;
int ans = -INF;
if(L <= mid) ans = max(ans, query(L, R, lson));
if(R > mid) ans = max(ans, query(L, R, rson));
return ans;
}
void change(int u, int v) {
while(top[u] != top[v]) {
if(dep[top[u]] < dep[top[v]]) {
swap(u, v);
}
update(id[top[u]], id[u], 1, cnt, 1);
u = fa[top[u]];
}
if(u != v) {
if(dep[u] > dep[v]) swap(u, v);
update(id[son[u]], id[v], 1, cnt, 1);
}
}
void Query(int u, int v) {
int ans = -INF;
while(top[u] != top[v]) {
if(dep[top[u]] < dep[top[v]]) {
swap(u, v);
}
ans = max(ans, query(id[top[u]], id[u], 1, cnt, 1));
u = fa[top[u]];
}
if(u != v) {
if(dep[u] > dep[v]) swap(u, v);
ans = max(ans, query(id[son[u]], id[v], 1, cnt, 1));
}
printf("%d\n", ans);
}
int u[maxn], v[maxn], c[maxn]; int main() {
#ifndef ONLINE_JUDGE
FIN
#endif
int n, T;
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
memset(head, -1, sizeof(head));
tot = cnt = 0;
for(int i = 1; i < n; i++) {
scanf("%d%d%d", &u[i], &v[i], &c[i]); //要用数组保存
add_edge(u[i], v[i], c[i]);
add_edge(v[i], u[i], c[i]);
}
prebuild();
build(1, cnt, 1);
char op[20];
int a, b;
while(1) {
scanf("%s", op);
if(op[0] == 'D') break;
scanf("%d%d", &a, &b);
if(op[0] == 'C') {
int tmp = dep[u[a]] > dep[v[a]] ? u[a] : v[a]; //找出深度大的那个点
update_pos(id[tmp], b, 1, cnt, 1); //更新进入深度大的点那条边
} else if(op[0] == 'N') change(a, b);
else if(op[0] == 'Q') Query(a, b);
}
}
return 0; }