首页 > 代码库 > 【bzoj1984】月下“毛景树” 树链剖分+线段树
【bzoj1984】月下“毛景树” 树链剖分+线段树
题目描述
毛毛虫经过及时的变形，最终逃过的一劫，离开了菜妈的菜园。 毛毛虫经过千山万水，历尽千辛万苦，最后来到了小小的绍兴一中的校园里。爬啊爬~爬啊爬~~毛毛虫爬到了一颗小小的“毛景树”下面，发现树上长着他最爱吃的毛毛果~~~ “毛景树”上有N个节点和N-1条树枝，但节点上是没有毛毛果的，毛毛果都是长在树枝上的。但是这棵“毛景树”有着神奇的魔力，他能改变树枝上毛毛果的个数： ? Change k w：将第k条树枝上毛毛果的个数改变为w个。 ? Cover u v w：将节点u与节点v之间的树枝上毛毛果的个数都改变为w个。 ? Add u v w：将节点u与节点v之间的树枝上毛毛果的个数都增加w个。 由于毛毛虫很贪，于是他会有如下询问： ? Max u v：询问节点u与节点v之间树枝上毛毛果个数最多有多少个。
输入
第一行一个正整数N。 接下来N-1行，每行三个正整数Ui，Vi和Wi，第i+1行描述第i条树枝。表示第i条树枝连接节点Ui和节点Vi，树枝上有Wi个毛毛果。 接下来是操作和询问，以“Stop”结束。
输出
对于毛毛虫的每个询问操作，输出一个答案。
样例输入
4
1 2 8
1 3 7
3 4 9
Max 2 4
Cover 2 4 5
Add 1 4 10
Change 1 16
Max 2 4
Stop
样例输出
9
16
题解
树剖+线段树傻X题
pushdown的时候顺序是先染色后加减，染色时把儿子的加减标记清空。
然后各种傻X操作就过了。
#include <cstdio>#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 , x[N] , y[N] , z[N] , r[N];int fa[N] , deep[N] , si[N] , bl[N] , pos[N] , tot;int w[N] , maxn[N << 2] , tag[N << 2] , cov[N << 2] , n;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 = 0; 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) { dfs2(k , c); for(i = head[x] ; i ; i = next[i]) if(to[i] != fa[x] && to[i] != k) dfs2(to[i] , to[i]); }}void pushup(int x){ maxn[x] = max(maxn[x << 1] , maxn[x << 1 | 1]);}void build(int l , int r , int x){ if(l == r) { maxn[x] = w[l]; return; } int mid = (l + r) >> 1; build(lson) , build(rson); pushup(x);}void pushdown(int x){ int ls = x << 1 , rs = x << 1 | 1; if(cov[x]) maxn[ls] = maxn[rs] = cov[x] , tag[ls] = tag[rs] = 0 , cov[ls] = cov[rs] = cov[x] , cov[x] = 0; if(tag[x]) maxn[ls] += tag[x] , maxn[rs] += tag[x] , tag[ls] += tag[x] , tag[rs] += tag[x] , tag[x] = 0;}void change(int b , int e , int c , int l , int r , int x){ if(b <= l && r <= e) { maxn[x] = c , tag[x] = 0 , cov[x] = c; return; } pushdown(x); int mid = (l + r) >> 1; if(b <= mid) change(b , e , c , lson); if(e > mid) change(b , e , c , rson); pushup(x);}void update(int b , int e , int a , int l , int r , int x){ if(b <= l && r <= e) { maxn[x] += a , tag[x] += a; return; } pushdown(x); int mid = (l + r) >> 1; if(b <= mid) update(b , e , a , lson); if(e > mid) update(b , e , a , rson); pushup(x);}int query(int b , int e , int l , int r , int x){ if(b <= l && r <= e) return maxn[x]; pushdown(x); int mid = (l + r) >> 1 , ans = 0; if(b <= mid) ans = max(ans , query(b , e , lson)); if(e > mid) ans = max(ans , query(b , e , rson)); return ans;}void solvechange(int x , int y , int c){ while(bl[x] != bl[y]) { if(deep[bl[x]] < deep[bl[y]]) swap(x , y); change(pos[bl[x]] , pos[x] , c , 1 , n , 1) , x = fa[bl[x]]; } if(deep[x] > deep[y]) swap(x , y); if(x != y) change(pos[x] + 1 , pos[y] , c , 1 , n , 1);}void solveupdate(int x , int y , int 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); if(x != y) update(pos[x] + 1 , pos[y] , a , 1 , n , 1);}int solvequery(int x , int y){ int ans = 0; while(bl[x] != bl[y]) { if(deep[bl[x]] < deep[bl[y]]) swap(x , y); ans = max(ans , query(pos[bl[x]] , pos[x] , 1 , n , 1)) , x = fa[bl[x]]; } if(deep[x] > deep[y]) swap(x , y); if(x != y) ans = max(ans , query(pos[x] + 1 , pos[y] , 1 , n , 1)); return ans;}int main(){ int i , a , b , c; scanf("%d" , &n); for(i = 1 ; i < n ; i ++ ) scanf("%d%d%d" , &x[i] , &y[i] , &z[i]) , add(x[i] , y[i]) , add(y[i] , x[i]); dfs1(1) , dfs2(1 , 1); for(i = 1 ; i < n ; i ++ ) r[i] = (deep[x[i]] > deep[y[i]] ? x[i] : y[i]) , w[pos[r[i]]] = z[i]; build(1 , n , 1); while(scanf("%s" , str) != EOF && str[1] != ‘t‘) { scanf("%d%d" , &a , &b); switch(str[1]) { case ‘h‘: change(pos[r[a]] , pos[r[a]] , b , 1 , n , 1); break; case ‘o‘: scanf("%d" , &c) , solvechange(a , b , c); break; case ‘d‘: scanf("%d" , &c) , solveupdate(a , b , c); break; default: printf("%d\n" , solvequery(a , b)); } } return 0;}
【bzoj1984】月下“毛景树” 树链剖分+线段树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。