首页 > 代码库 > 【bzoj2836】魔法树 树链剖分+线段树

【bzoj2836】魔法树 树链剖分+线段树

题目描述

技术分享

 

输入

技术分享

输出

技术分享

样例输入

4
0 1
1 2
2 3
4
Add 1 3 1
Query 0
Query 1
Query 2

样例输出

3
3
2


题解

树剖+线段树模板题,不过为什么写的人这么少。。。

注意需要开long long

#include <cstdio>#include <algorithm>#define N 100010#define lson l , mid , x << 1#define rson mid + 1 , r , x << 1 | 1using namespace std;typedef long long ll;int head[N] , to[N << 1] , next[N << 1] , cnt;int fa[N] , deep[N] , si[N] , bl[N] , pos[N] , last[N] , tot , n;ll sum[N << 2] , tag[N << 2];char str[10];void add(int x , int y){	to[++cnt] = y , next[cnt] = head[x] , head[x] = cnt;}void dfs1(int x){	int i;	si[x] = 1;	for(i = head[x] ; i ; i = next[i])		if(to[i] != fa[x])			fa[to[i]] = x , deep[to[i]] = deep[x] + 1 , dfs1(to[i]) , si[x] += si[to[i]];}void dfs2(int x , int c){	int i , k = n;	bl[x] = c , pos[x] = ++tot;	for(i = head[x] ; i ; i = next[i])		if(to[i] != fa[x] && si[k] < si[to[i]])			k = to[i];	if(k != n)	{		dfs2(k , c);		for(i = head[x] ; i ; i = next[i])			if(to[i] != fa[x] && to[i] != k)				dfs2(to[i] , to[i]);	}	last[x] = tot;}void pushup(int x){	sum[x] = sum[x << 1] + sum[x << 1 | 1];}void pushdown(int l , int r , int x){	if(tag[x])	{		int mid = (l + r) >> 1;		sum[x << 1] += tag[x] * (mid - l + 1) , tag[x << 1] += tag[x];		sum[x << 1 | 1] += tag[x] * (r - mid) , tag[x << 1 | 1] += tag[x];		tag[x] = 0;	}}void update(int b , int e , ll a , int l , int r , int x){	if(b <= l && r <= e)	{		sum[x] += a * (r - l + 1) , tag[x] += a;		return;	}	pushdown(l , r , x);	int mid = (l + r) >> 1;	if(b <= mid) update(b , e , a , lson);	if(e > mid) update(b , e , a , rson);	pushup(x);}ll query(int b , int e , int l , int r , int x){	if(b <= l && r <= e) return sum[x];	pushdown(l , r , x);	int mid = (l + r) >> 1;	ll ans = 0;	if(b <= mid) ans += query(b , e , lson);	if(e > mid) ans += query(b , e , rson);	return ans;}void solveupdate(int x , int y , ll a){	while(bl[x] != bl[y])	{		if(deep[bl[x]] < deep[bl[y]]) swap(x , y);		update(pos[bl[x]] , pos[x] , a , 1 , n , 1);		x = fa[bl[x]];	}	if(deep[x] > deep[y]) swap(x , y);	update(pos[x] , pos[y] , a , 1 , n , 1);}int main(){	int m , i , x , y;	ll z;	scanf("%d" , &n);	for(i = 1 ; i < n ; i ++ ) scanf("%d%d" , &x , &y) , add(x , y) , add(y , x);	fa[0] = -1 , dfs1(0) , dfs2(0 , 0);	scanf("%d" , &m);	while(m -- )	{		scanf("%s%d" , str , &x);		if(str[0] == ‘Q‘) printf("%lld\n" , query(pos[x] , last[x] , 1 , n , 1));		else scanf("%d%lld" , &y , &z) , solveupdate(x , y , z);	}	return 0;}

 

 

【bzoj2836】魔法树 树链剖分+线段树