[TIOJ] 1228. Phh多層次傳銷公司

題目連結:http://tioj.infor.org/problems/1228

---

本題是建中資訊校內複賽題，當時我在寫的時候完全不會線段樹甚麼的，所以我那時是直接照著做，然後稍微二分搜一下他的區間，就拿到了第二組subtask，因此比完之後我一直以為這題很簡單，直到聽完題解說要把樹壓扁、開BIT，我才發現原來沒有想像中的簡單。
--以上廢話--
本題把樹壓扁後就變成單點修改區間查詢的序列問題了，但什麼是把樹壓扁呢，在本題中可以發現我們會修改以及查詢的其實都是邊權，所以其實可以用一定的方法幫這些邊編號，而因為我們在查區間和時是用DFS的方法去跑，所以不妨就用DFS時碰到邊的順序幫它編號，但記得要開個mapping能讓它之後詢問跟修改時知道要對幾號做動作，大概就醬吧。
p.s本題記憶體有點卡，不能寫線段樹，只能寫BIT(至少我就醬被梗了一段時間

#include <bits/stdc++.h>
using namespace std;
#define N 1000000
#define lowbit(x) ((x)&-(x))
struct node{
	int child,val;
};
struct dian{
	int l,r;
};
vector<node> tree[N+5];
dian dianMap[N+5];
int bianMap[N+5];
int BIT[N+5];

int n,q;
int counter=0;
int arr[N];
void foldTree(int);
void buildBIT();
void edit(int,int);
inline int sum(int);
int query(int,int);

int main(){
	scanf("%d%d",&n,&q);
	for(int i=0;i<n-1;i++){
		int a,b,m;
		scanf("%d%d%d",&a,&b,&m);
		node tp;
		tp.child=b;
		tp.val=m;
		tree[a].push_back(tp);
	}
	foldTree(0);
	buildBIT();
	for(int i=0;i<q;i++){
		int type;
		scanf("%d",&type);
		if(type){
			int w;
			scanf("%d",&w);
			int ans = query(dianMap[w].l, dianMap[w].r);
			printf("%d\n",ans<<1);
		}else{
			int w,v;
			scanf("%d%d",&w,&v);
			edit(bianMap[w]+1,v-arr[bianMap[w]]);
			arr[bianMap[w]] = v;
		}
	}
	return 0;
}

void foldTree(int w){
	dianMap[w].l=counter;
	for(int i=0;i<tree[w].size();i++){
		bianMap[tree[w][i].child]=counter;
		arr[counter++]=tree[w][i].val;
		foldTree(tree[w][i].child);
	}
	dianMap[w].r=counter;
}

void edit(int x,int d){
	while(x<=n){
		BIT[x]+=d;
		x+=lowbit(x);
	}
}
inline int sum(int x){
	int ans=0;
	while(x>0){
		ans+=BIT[x];
		x-=lowbit(x);
	}
	return ans;
}
int query(int l,int r){
	return sum(r)-sum(l);
}

void buildBIT(){
	for(int i=0;i<n;i++){
		edit(i+1,arr[i]);
	}
}