[TIOJ] 1493. 三個農夫

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

---

本題要求在樹上對一個節點單點加值或是問一個節點及其子樹的和，顯然直接照著做會TLE，所以不妨考慮把樹壓扁後的序列，修改一個節點的值就是對序列作單點修改，問子樹的話也會剛好是一個連續的區間，所以就直接作區間詢問就好。單點修改，區間查詢就是一個BIT支援的操作，所以就開三個BIT把三種果實維護好即可。

#include <bits/stdc++.h>
using namespace std;
#define PB push_back
typedef pair<int, int> PII;
#define FF first
#define SS second

const int N = 1000000 + 5;

vector<int> g[N];
int st[N], ed[N], timer=1;

void dfs(int,int);

struct BIT{
	int arr[2*N];

	inline int lowbit(int x){
		return x&(-x);
	}
	void add(int w, int c){
		while(w<=timer){
			arr[w]+=c;
			w+=lowbit(w);
		}
	}
	int query(int l, int r){
		return query(r-1) - query(l-1);
	}
	int query(int w){
		int r=0;
		while(w){
			r+=arr[w];
			w-=lowbit(w);
		}
		return r;
	}
} trees[3];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n;cin>>n;
	for(int i=0;i<n-1;i++){
		int u, v; cin>>u>>v;
		g[u].PB(v);
		g[v].PB(u);
	}
	dfs(1, 1);
	int m;cin>>m;
	while(m--){
		string cmd; cin>>cmd;
		if(cmd == "Grow"){
			int w, k ,c;cin>>w>>k>>c;
			if(((k==0 or k==1) and w==1) or (k==2 and ed[w]-st[w]==1))
				cout<<"Error\n";
			else
				trees[k].add(st[w], c);
		}else if(cmd == "Drop"){
			int w, k, c; cin>>w>>k>>c;
			if(trees[k].query(st[w], st[w]+1) < c)
				cout<<"Error\n";
			else
				trees[k].add(st[w], -c);
		}else if(cmd == "Query"){
			int w;cin>>w;
			cout<<trees[0].query(st[w], ed[w]);
			for(int i=1;i<3;i++) cout<<' '<<trees[i].query(st[w], ed[w]);
			cout<<'\n';
		}
	}
	return 0;
}

void dfs(int w, int f){
	st[w] = timer++;
	for(auto i:g[w]) if(i!=f)
		dfs(i, w);
	ed[w] = timer++;
}