首页 > 代码库 > 【bzoj3589】动态树 树链剖分+线段树
【bzoj3589】动态树 树链剖分+线段树
题目描述
别忘了这是一棵动态树, 每时每刻都是动态的. 小明要求你在这棵树上维护两种事件
事件0:这棵树长出了一些果子, 即某个子树中的每个节点都会长出K个果子.
事件1:小明希望你求出几条树枝上的果子数. 一条树枝其实就是一个从某个节点到根的路径的一段. 每次小明会选定一些树枝, 让你求出在这些树枝上的节点的果子数的和. 注意, 树枝之间可能会重合, 这时重合的部分的节点的果子只要算一次.
输入
第一行一个整数n(1<=n<=200,000), 即节点数.
接下来n-1行, 每行两个数字u, v. 表示果子u和果子v之间有一条直接的边. 节点从1开始编号.
在接下来一个整数nQ(1<=nQ<=200,000), 表示事件.
最后nQ行, 每行开头要么是0, 要么是1.
如果是0, 表示这个事件是事件0. 这行接下来的2个整数u, delta表示以u为根的子树中的每个节点长出了delta个果子.
如果是1, 表示这个事件是事件1. 这行接下来一个整数K(1<=K<=5), 表示这次询问涉及K个树枝. 接下来K对整数u_k, v_k, 每个树枝从节点u_k到节点v_k. 由于果子数可能非常多, 请输出这个数模2^31的结果.
输出
对于每个事件1, 输出询问的果子数.
样例输入
5
1 2
2 3
2 4
1 5
3
0 1 1
0 2 3
1 2 3 1 1 4
样例输出
13
题解
树链剖分+线段树
一眼看上去树剖线段树傻*题，然而实际看上去却不是这样。
由于每次选择了某些链，它们重叠的部分是不能计算的，所以情况比较复杂。
我们可以换一个角度去思考，把“计算链的点权和”改为“标记链上的点，并计算被标记的点的点权和”。
这有什么用？
由于区间的标记仅为0/1，所以对某段区间打标记时可以用线段树维护和，并不需要加减性质。
于是有：将每条链对应的每段区间在线段树中标记上，然后统计线段树中所有被标记的点的权值和，最后删除所有点的标记。
树剖+线段树区间修改区间查询，时间复杂度$O(Qk\log ^2n)$。
需要稍微注意一下双标记的处理，如果有标记的标记（这话这么别扭= = 选择标记）则应当立刻优先处理。
至于mod maxlongint，可以使用int自然溢出，最后结果和maxlongint取与。
至今不知道“所有链随机生成且所有链上的点的最近公共祖先为链的端点”这个条件有什么用= =
#include <cstdio>#include <cstring>#include <algorithm>#define N 200010#define lson l , mid , x << 1#define rson mid + 1 , r , x << 1 | 1using namespace std;int head[N] , to[N << 1] , next[N << 1] , cnt;int fa[N] , deep[N] , si[N] , bl[N] , pos[N] , last[N] , tot;int sum[N << 2] , val[N << 2] , add[N << 2] , tag[N << 2] , n;void ins(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 = 0; bl[x] = c , pos[x] = ++tot; for(i = head[x] ; i ; i = next[i]) if(to[i] != fa[x] && si[to[i]] > si[k]) k = to[i]; if(k) { 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] , val[x] = val[x << 1] + val[x << 1 | 1];}void pushdown(int l , int r , int x){ if(add[x]) { int mid = (l + r) >> 1; sum[x << 1] += add[x] * (mid - l + 1) , sum[x << 1 | 1] += add[x] * (r - mid); add[x << 1] += add[x] , add[x << 1 | 1] += add[x] , add[x] = 0; } if(~tag[x]) { val[x << 1] = sum[x << 1] * tag[x] , val[x << 1 | 1] = sum[x << 1 | 1] * tag[x]; tag[x << 1] = tag[x << 1 | 1] = tag[x] , tag[x] = -1; }}void update(int b , int e , int a , int l , int r , int x){ if(b <= l && r <= e) { sum[x] += a * (r - l + 1) , add[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);}void color(int b , int e , int c , int l , int r , int x){ if(b <= l && r <= e) { val[x] = c * sum[x] , tag[x] = c; return; } pushdown(l , r , x); int mid = (l + r) >> 1; if(b <= mid) color(b , e , c , lson); if(e > mid) color(b , e , c , rson); pushup(x);}void solve(int x , int y){ while(bl[x] != bl[y]) { if(deep[bl[x]] < deep[bl[y]]) swap(x , y); color(pos[bl[x]] , pos[x] , 1 , 1 , n , 1) , x = fa[bl[x]]; } if(deep[x] > deep[y]) swap(x , y); color(pos[x] , pos[y] , 1 , 1 , n , 1);}int main(){ int m , i , opt , k , x , y; scanf("%d" , &n); for(i = 1 ; i < n ; i ++ ) scanf("%d%d" , &x , &y) , ins(x , y) , ins(y , x); dfs1(1) , dfs2(1 , 1); memset(tag , -1 , sizeof(tag)); scanf("%d" , &m); while(m -- ) { scanf("%d" , &opt); if(opt == 0) scanf("%d%d" , &x , &y) , update(pos[x] , last[x] , y , 1 , n ,1); else { scanf("%d" , &k); while(k -- ) scanf("%d%d" , &x , &y) , solve(x , y); printf("%d\n" , val[1] & 0x7fffffff); color(1 , n , 0 , 1 , n , 1); } } return 0;}
【bzoj3589】动态树 树链剖分+线段树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。