看到这题很开心啊，有印象跟以前做过的很像，貌似最近就做过一个，以时间戳为区间来建立树状数组，然后一开始我以为题意是，给x点加val，它以下的所有节点都加-val；所以一开始就以 加 和 减 建立了两个树状数组，最后 减去就是答案，写完发现跟案例对不上啊，读了题目也没发现读错了，对于那句话 我理解错了，后来看了 这个：
http://blog.csdn.net/keshuai19940722/article/details/18967661
仔细看看处理部分，我还以为分奇偶性有规律呢，后来才发现读错题目了，原来是x点加val,与它直接相连的子节点加上-val，它的子节点的子节点又加上val，以此类推。。。哈哈。。哭
跟以前那类题目做法相同，对于这棵树，进行dfs,同时记录当前层数距离跟的关系，用奇偶数来表示，然后再以各个节点被dfs的时间戳 来建立区间 让树状数组映射上去，最后奇偶分开，加的在一个树状数组里，减去的在另一个里面，然后 最后求单点值的时候 就是自己这个点 所属的 距离根节点的关系，也就是自己应该加上的值，再减去对应的另一个树状数组里的应该减去的值，然后 一开始 各个节点本身具有的值 并没有加进树状数组里，还得加上原本具有的值，这样就是答案了
然后又用线段树做了一下，也是以时间戳来搞，同时记录这个节点距离根的奇偶性，然后也是建立两颗线段树，一个记录奇数处理，一个记录偶数处理，结果不知哪里写错了，又改了很久，不行又重新写了一下，真是学啥忘啥。。。
树状数组的：
立即学习“前端免费学习笔记（深入）”；
int n;int m;int c[2][200000 * 2 + 55];typedef struct Node { int l,r,val; int now;};Node node[200000 + 55];vector<int > G[200000 + 55];int cnt;void init() { memset(c,0,sizeof(c)); for(int i=0;i<200000 + 55;i++)G[i].clear();}bool input() { while(cin>>n>>m) { for(int i=1;i<=n;i++)cin>>node[i].val; int tmp = n - 1; while(tmp--) { int u,v; scanf("%d %d",&u,&v); G[u].push_back(v); G[v].push_back(u); } return false; } return true;}int lowbit(int x) { return x&(-x);}void add(int i,int val,int *aa) { while(i <= 2 * n) { aa[i] += val; i += lowbit(i); }}int get_sum(int i,int *aa) { int sum = 0; while(i > 0) { sum += aa[i]; i -= lowbit(i); } return sum;}void dfs(int u,int pre,int tot) { node[u].l = cnt++; node[u].now = tot; for(int i=0;i<G[u].size();i++) { int v = G[u][i]; if(v == pre)continue; dfs(v,u,tot^1); } node[u].r = cnt++;}void cal() { cnt = 1; dfs(1,-1,0); while(m--) { int type; cin>>type; if(type == 1) { int x,y; cin>>x>>y; //int tmp = node[x].now; //int aa = node[x].l; //int bb = node[x].r; add(node[x].l,y,c[node[x].now]); add(node[x].r + 1,-y,c[node[x].now]); } else { int x; cin>>x; //int aa = (get_sum(node[x].l,c[node[x].d]) /*- get_sum(node[x].l - 1,c[node[x].d])*/); //int bb = (get_sum(node[x].l,c[node[x].d^1])/* - get_sum(node[x].l - 1,c[node[x].d^1])*/); //int cc = 0; int ans = get_sum(node[x].l,c[node[x].now]) - get_sum(node[x].l,c[node[x].now^1]); ans += node[x].val; cout<<ans<<endl; } }}void output() {}int main() { while(true) { init(); if(input())return 0; cal(); output(); } return 0;}立即学习“前端免费学习笔记（深入）”；
线段树的：
立即学习“前端免费学习笔记（深入）”；
const int N = 200000 + 55;int n;int m;int nnum[N + 55];int le[N + 55],ri[N + 55],belong[N + 55];int head[N + 55];typedef struct Node { int l,r; ll sum; int lazy;};Node tree_even[N * 4 + 55],tree_odd[N * 4 + 55];typedef struct NODE { int fro,to; int nex;};NODE edge[2 * N + 55];int tot;int cnt;void add(int u,int v) { edge[tot].fro = u; edge[tot].to = v; edge[tot].nex = head[u]; head[u] = tot++;}void dfs(int u,int pre,int d) { le[u] = ++cnt; for(int i=head[u];i!=-1;i=edge[i].nex) { int v = edge[i].to; if(v == pre)continue; dfs(v,u,d^1); } belong[le[u]] = d; ri[le[u]] = cnt;}void push_up(int id,Node *tree) { tree[id].sum = tree[id<<1].sum + tree[id<<1|1].sum;}void push_down(int id,Node *tree) { if(tree[id].lazy == 0)return ; tree[id].sum += (tree[id].r - tree[id].l + 1) * tree[id].lazy; if(tree[id].l == tree[id].r) { tree[id].lazy = 0; return ; } tree[id<<1].lazy += tree[id].lazy; tree[id<<1|1].lazy += tree[id].lazy; tree[id].lazy = 0;}void build(int l,int r,int id,Node *tree) { tree[id].l = l; tree[id].r = r; tree[id].lazy = 0; if(l == r) { tree[id].sum = 0ll; return ; } int mid = (l + r)>>1; build(l,mid,id<<1,tree); build(mid + 1,r,id<<1|1,tree); push_up(id,tree);}void update(int l,int r,int id,ll val,Node *tree) { if(tree[id].l == l && tree[id].r == r) { tree[id].lazy += val; push_down(id,tree); return ; } push_down(id,tree); int mid = (tree[id].l + tree[id].r)>>1; if(r <= mid)update(l,r,id<<1,val,tree); else if(l > mid)update(l,r,id<<1|1,val,tree); else { update(l,mid,id<<1,val,tree); update(mid + 1,r,id<<1|1,val,tree); } push_up(id,tree);}ll query(int l,int r,int id,Node *tree) { if(tree[id].l == l && tree[id].r == r) { push_down(id,tree); return tree[id].sum; } push_down(id,tree); int mid = (tree[id].l + tree[id].r)>>1; ll ret = 0ll; if(r <= mid)ret += query(l,r,id<<1,tree); else if(l > mid)ret += query(l,r,id<<1|1,tree); else { ret += query(l,mid,id<<1,tree); ret += query(mid + 1,r,id<<1|1,tree); } return ret;}void init() { memset(tree_even,0,sizeof(tree_even)); memset(tree_odd,0,sizeof(tree_odd)); memset(head,-1,sizeof(head)); tot = 1; cnt = 0;}bool input() { while(cin>>n>>m) { for(int i=1;i<=n;i++)cin>>nnum[i]; for(int i=1;i<n;i++) { int u,v; cin>>u>>v; add(u,v); add(v,u); } return false; } return true;}void cal() { dfs(1,-1,1); build(1,n,1,tree_even); build(1,n,1,tree_odd); while(m--) { int type; cin>>type; if(type == 1) { int x,y; cin>>x>>y; int left = le[x]; int right = ri[left]; if(belong[left]&1) update(left,right,1,y,tree_odd); else update(left,right,1,y,tree_even); } else { int x; cin>>x; int left = le[x]; ll ans; if(belong[left]&1) ans = query(left,left,1,tree_odd) - query(left,left,1,tree_even); else ans = query(left,left,1,tree_even) - query(left,left,1,tree_odd); ans += nnum[x]; cout<<ans<<endl; } }}void output() {}int main() { while(true) { init(); if(input())return 0; cal(); output(); } return 0;}立即学习“前端免费学习笔记（深入）”；
HTML怎么学习？HTML怎么入门？HTML在哪学？HTML怎么学才快？不用担心，这里为大家提供了HTML速学教程(入门课程)，有需要的小伙伴保存下载就能学习啦！
Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号
259
收藏
