首页 > 代码库 > 【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】魔法树 树链剖分+线段树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。