BZOJ1036 [ZJOI2008]树的统计Count 【树链剖分】

tonyfang posted @ 2016年10月13日 21:35 in BZOJ with tags C++ OI , 764 阅读

日常复习模板系列。今日用时30min+30min=1h(后面的是调试)

记一些奇怪的trick:一直走top的时候判断dep[top[u]]和dep[top[v]]可以避免出现访问0节点。

 

# include <stdio.h>
# include <algorithm>
// # include <bits/stdc++.h>

using namespace std;

const int N = 30010, M = 60010;
int n, tot=0, head[N], next[M], to[M], we[N], DFN=0, son[N], sz[N], pos[N], dep[N], fa[N], top[N];

inline void add(int u, int v) {
	++tot; next[tot]=head[u]; head[u]=tot; to[tot]=v;
}

inline void dfs1(int x, int fat) {
	fa[x] = fat; dep[x] = dep[fat] + 1;
	sz[x] = 1; son[x] = -1;
	for (int i=head[x]; i; i=next[i]) {
		if(to[i] == fat) continue;
		dfs1(to[i], x);
		if(son[x] == -1 || sz[son[x]] < sz[to[i]]) son[x] = to[i];
		sz[x] = sz[x] + sz[to[i]];
	}
}

inline void dfs2(int x, int fa, int tp) {
	pos[x] = ++DFN; top[x] = tp;
	if(son[x] != -1) dfs2(son[x], x, tp);
	for (int i=head[x]; i; i=next[i]) {
		if(to[i] == fa || to[i] == son[x]) continue;
		dfs2(to[i], x, to[i]);
	}
}

typedef long long ll;
ll w[N<<2], lazy[N<<2], mx[N<<2];
  
inline void pushdown(int x, int l, int r) {
    if(lazy[x] == -1) return;
    int mid = l+r >> 1;
    w[x<<1] = lazy[x] * (mid - l + 1);
    w[x<<1|1] = lazy[x] * (r - (mid+1) + 1);
    mx[x<<1] = mx[x<<1] + lazy[x];
    mx[x<<1|1] = mx[x<<1|1] + lazy[x];
    lazy[x<<1] = lazy[x];
    lazy[x<<1|1] = lazy[x];
    lazy[x] = -1;
}
  
inline void change(int x, int l, int r, int L, int R, int delta) {
    if(L <= l && r <= R) {
        w[x] += delta*(r - l + 1);
        mx[x] = mx[x] + delta;
        lazy[x] = delta;
        return ;
    }
    pushdown(x, l, r);
    int mid = l+r >> 1;
    if(L > mid) change(x<<1|1, mid+1, r, L, R, delta);
    else if(R <= mid) change(x<<1, l, mid, L, R, delta);
    else {
        change(x<<1, l, mid, L, mid, delta);
        change(x<<1|1, mid+1, r, mid+1, R, delta);
    }
    w[x] = w[x<<1] + w[x<<1|1];
    mx[x] = max(mx[x<<1], mx[x<<1|1]);
}
  
inline ll querysum(int x, int l, int r, int L, int R) {
    if(L <= l && r <= R) return w[x];
    pushdown(x, l, r);
    int mid = l+r >> 1;
    if(L > mid) return querysum(x<<1|1, mid+1, r, L, R);
    else if(R <= mid) return querysum(x<<1, l, mid, L, R);
    else return querysum(x<<1, l, mid, L, mid) + querysum(x<<1|1, mid+1, r, mid+1, R);
}

inline ll querymax(int x, int l, int r, int L, int R) {
    if(L <= l && r <= R) return mx[x];
    pushdown(x, l, r);
    int mid = l+r >> 1;
    if(L > mid) return querymax(x<<1|1, mid+1, r, L, R);
    else if(R <= mid) return querymax(x<<1, l, mid, L, R);
    else {
		ll ql = querymax(x<<1, l, mid, L, mid), qr = querymax(x<<1|1, mid+1, r, mid+1, R);
		return max(ql, qr);
	}
}

inline ll getmax(int u, int v) {
	ll ret = -66666, tu, tv;
	while(top[u] != top[v]) {
		if(dep[top[u]] < dep[top[v]]) swap(u, v);
		tu = querymax(1, 1, n, pos[top[u]], pos[u]);
		ret = max(ret, tu);
		u = fa[top[u]];
	}
	if(dep[u] <= dep[v]) {
		tu = querymax(1, 1, n, pos[u], pos[v]);
	} else tu = querymax(1, 1, n, pos[v], pos[u]);
	ret = max(ret, tu);
	return ret;
}

inline ll getsum(int u, int v) {
	ll ret = 0, tu;
	while(top[u] != top[v]) {
		if(dep[top[u]] < dep[top[v]]) swap(u, v);
		tu = querysum(1, 1, n, pos[top[u]], pos[u]);
		ret = ret + tu;
		u = fa[top[u]];
	}
	if(dep[u] <= dep[v]) {
		tu = querysum(1, 1, n, pos[u], pos[v]);
	} else tu = querysum(1, 1, n, pos[v], pos[u]);
	ret = ret + tu;
	return ret;
}

int main() {
	scanf("%d", &n);
	for (int i=1, u, v; i<n; ++i) {
		scanf("%d%d", &u, &v);
		add(u, v);
		add(v, u);
	}
	dfs1(1, 0);
	dfs2(1, 0, 1);
	for (int i=1; i<(n<<2); ++i) lazy[i] = -1;
	for (int i=1; i<=n; ++i) {
		scanf("%d", &we[i]);
		change(1, 1, n, pos[i], pos[i], we[i]);
	}
	int q;
	char opt[8];
	scanf("%d", &q);
	while(q--) {
		scanf("%s", opt);
		if(opt[1] == 'M') {
			int u, v;
			scanf("%d%d", &u, &v);
			// qmax
			printf("%lld\n", getmax(u, v));
		} else if(opt[1] == 'S') {
			// qsum
			int u, v;
			scanf("%d%d", &u, &v);
			printf("%lld\n", getsum(u, v));
		} else {
			// change
			int x, de;
			scanf("%d%d", &x, &de);
			change(1, 1, n, pos[x], pos[x], de-we[x]);
			we[x]=de;
		}
	}
	return 0;
}
11th Question Paper 说:
2023年2月16日 21:25

11th Question Paper 2024 Every one of the students are right now sitting tight for the 11th test Model Paper to be Download, so need to reveal to you that as per the data got from the sources as of late, 11th Question Paper 2024 The board will deliver its 11th test Model Paper, realizing that it will be made accessible to you. So continue to check this post consistently.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter