UVA1674 闪电的能量树剖

题面

水。树剖模板
#include <cstdio>

#include <cstring>

#include <algorithm>

#define MAXN 50005

#define sl (x<<1)

#define sr (x<<1|1)

#define ll long long

using namespace std;

int head[MAXN],vv[MAXN*2],nxt[MAXN*2],tot;

inline void add_edge(int u, int v){

	vv[++tot]=v;

	nxt[tot]=head[u];

	head[u]=tot;

}

int n,q;

int fa[MAXN],dep[MAXN],sz[MAXN],mxs[MAXN];

void dfs1(int u, int f){

	fa[u]=f;

	dep[u]=dep[f]+1;

	sz[u]=1;

	int mxsz=-1;

	mxs[u]=0;

	for(int i=head[u];i;i=nxt[i]){

		int v=vv[i];

		if(v==f) continue;

		dfs1(v,u);

		sz[u]+=sz[v];

		if(mxsz<sz[v]){

			mxsz=sz[v];

			mxs[u]=v;

		}

	}

}

int idx[MAXN],topf[MAXN],cnt;

void dfs2(int u, int top){

	topf[u]=top;

	idx[u]=++cnt;

	if(mxs[u]==0) return;

	dfs2(mxs[u], top);

	for(int i=head[u];i;i=nxt[i]){

		int v=vv[i];

		if(v==fa[u]||v==mxs[u]) continue;

		dfs2(v,v);

	}

}

struct nod{

	int l,r,val,lazy;

} tre[MAXN*4];

void buildt(int x, int l, int r){

	tre[x].l=l,tre[x].r=r,tre[x].val=0,tre[x].lazy=0;

	if(l==r) return;

	int mid=(tre[x].l+tre[x].r)>>1;

	buildt(sl, l, mid);

	buildt(sr, mid+1, r);

}

void push_down(int x){

	if(tre[x].lazy==0) return;

	tre[sl].lazy+=tre[x].lazy;

	tre[sr].lazy+=tre[x].lazy;

	tre[sl].val+=tre[x].lazy*(tre[sl].r-tre[sl].l+1);

	tre[sr].val+=tre[x].lazy*(tre[sr].r-tre[sr].l+1);

	tre[x].lazy=0;

}

void change(int x, int l, int r, int val){

	if(l<=tre[x].l&&tre[x].r<=r){

		tre[x].val+=val*(tre[x].r-tre[x].l+1);

		tre[x].lazy+=val;

		return;

	}

	push_down(x);

	int mid=(tre[x].l+tre[x].r)>>1;

	if(l<=mid) change(sl, l, r, val);

	if(mid<r) change(sr, l, r, val);

	tre[x].val=tre[sl].val+tre[sr].val;

}

int query(int x, int qx){

	if(tre[x].l==tre[x].r) return tre[x].val;

	push_down(x);

	int mid=(tre[x].l+tre[x].r)>>1;

	if(qx<=mid) return query(sl, qx);

	else return query(sr, qx);

}

void tre_change(int a, int b, int val){

	while(topf[a]!=topf[b]){

		if(dep[topf[a]]<dep[topf[b]]) swap(a,b);

		change(1, idx[topf[a]], idx[a], val);

		a=fa[topf[a]];

	}

	if(dep[a]<dep[b]) swap(a,b);

	change(1, idx[b], idx[a], val);

}

int tre_query(int x){

	return query(1, idx[x]);

}

void init(){

	memset(head, 0, sizeof(head));

	cnt=tot=0;

}

int main()

{

	int T;

	scanf("%d", &T);

	for(int z=1;z<=T;++z){

		printf("Case #%d:\n", z);

		init();

		scanf("%d", &n);

		for(int i=1;i<=n-1;++i){

			int u,v;scanf("%d %d", &u, &v);

			++u,++v;

			add_edge(u,v);

			add_edge(v,u);

		}

		dfs1(1,1);

		dfs2(1,1);

		buildt(1, 1, n);

		scanf("%d", &q);

		while(q--){

			int a,b,c;scanf("%d %d %d", &a, &b, &c);

			++a,++b;

			tre_change(a,b,c);

		}

		for(int i=1;i<=n;++i) printf("%d\n", query(1, idx[i]));

	}

	return 0;

}
巴特西

UVA1674 闪电的能量树剖

UVA1674 闪电的能量树剖

最新文章

热门文章

巴特西

UVA1674 闪电的能量 树剖

UVA1674 闪电的能量 树剖

最新文章

热门文章

UVA1674 闪电的能量树剖

UVA1674 闪电的能量树剖
