题解 P3833 【[SHOI2012]魔法树】

题目

很显然这是个树刨的板子，树上链查询和子树查询

注意：

1.这个点的树根为 0 而不是 1 所以注意读图时点标号 +1 就解决了

2.注意数据范围\(2^{32}\)

然后板子就能过了

node

#include <iostream>

#include <cstdio>

#define  N  100005

#define int long long

#define lson rt << 1

#define rson rt << 1|1

using namespace std;

int n,m,r;

int pre[N],dep[N],fa[N],son[N],siz[N],top[N],dfn[N],dfn2[N],cnt;

namespace Seg{

	struct Tree{

		int sum,len,lazy;

	}tree[N << 1];

	void push_up(int rt){

		tree[rt].sum = tree[lson].sum + tree[rson].sum;

	}

	void build(int rt,int l,int r){

		tree[rt].len = r - l + 1;

		if(l == r){

		   tree[rt].sum = 0;

			return;

		}

		int mid = (l + r)>>1;

		build(lson, l, mid);

		build(rson, mid + 1, r);

		push_up(rt);

	}

	void pushdown(int rt) {

		if (tree[rt].lazy){

		  tree[lson].sum +=  tree[rt].lazy * tree[lson].len;

		  tree[rson].sum +=  tree[rt].lazy * tree[rson].len;

		  tree[lson].lazy +=  tree[rt].lazy;

		  tree[rson].lazy +=  tree[rt].lazy;

		  tree[rt].lazy = 0;

		}

	}

	void update(int rt,int k,int l,int r,int L,int R){

		if(l >= L && r <= R){

			tree[rt].sum +=  k * tree[rt].len;

			tree[rt].lazy += k;

			return;

		}

		pushdown(rt);

		int mid = (l + r) >> 1;

		if(mid >= L) update(lson, k, l, mid, L, R);

		if(mid < R) update(rson, k, mid + 1, r, L, R);

		push_up(rt);

	}

	int query(int rt,int l,int r,int L,int R){

		if(l >= L&& r <= R) return tree[rt].sum;

		pushdown(rt);

		int mid = (l + r)>>1,ans = 0;

		if(L <= mid) ans += query(lson,l,mid,L,R);

		if(mid < R)  ans += query(rson,mid + 1,r,L,R);

		return ans;

	}

}

namespace Cut {

	struct edge{

		int v,nxt;

	}e[N << 1];

	int head[N],js;

	void add_edge(int u,int v){

     e[++js].v = v;e[js].nxt = head[u];head[u] = js;

	}

	void dfs(int x,int f,int d){

	  dep[x] = d,fa[x] = f,siz[x] = 1;

	  for(int i = head[x]; i;i = e[i].nxt){

	  	   int v = e[i].v;

	  	   if(v != fa[x]){

	  	       dfs(v, x, d + 1);

			   siz[x] += siz[v];

			   if(!son[x]||siz[son[x]] < siz[v])

			   	  son[x] = v;

		   }

	  }

	}

    void dfs2(int x,int tp){

    	dfn[x] =++cnt,pre[cnt] = x,top[x] = tp;

		if(son[x]) dfs2(son[x],tp);

		for(int i = head[x]; i; i = e[i].nxt){

			 int v = e[i].v;

			 if(v != fa[x]&&v != son[x]) dfs2(v,v);

		}

	}

   int query_tree(int x){

   	   return Seg::query(1, 1, n, dfn[x],dfn[x] + siz[x] - 1);

   }

   void change_sum(int x,int y,int k){

		while(top[x] != top[y]){

			if(dep[top[x]] < dep[top[y]]) swap(x,y);

			Seg::update(1, k, 1, n,dfn[top[x]], dfn[x]);

		    x = fa[top[x]];

		}

		if(dep[x] > dep[y]) swap(x,y);

		Seg::update(1, k, 1, n,dfn[x], dfn[y]);

   }

}

signed main() {

	int Q;

	cin>>n;

	for (int i = 1, x, y; i < n; i++) {

	  cin>>x>>y;

	  Cut::add_edge(x + 1, y + 1);

	  Cut::add_edge(y + 1, x + 1);

	}

	Cut::dfs(1, 0, 1);

	Cut::dfs2(1, 1);

	Seg::build(1, 1, n);

	cin >> Q;

	while(Q--){

		int x,y,z;

	  	char opt;

		cin >> opt;

		if (opt == 'A') cin>>x>>y>>z,Cut::change_sum(x + 1, y + 1, z);

		if (opt == 'Q') cin>>x,printf("%lld\n", Cut::query_tree(x + 1));

	}

}

巴特西

题解 P3833 【[SHOI2012]魔法树】

题目

注意：

node

最新文章

热门文章