题目链接:Codeforces 383C Propagating tree
题目大意:给出一颗有n个节点并一1为根节点的树,每个节点有它的权值,现在进行m次操作,操作分为添加和查询,当一个节点的权值添加val,则它的孩子节点的权值要添加-b。
解题思路:首先通过dfs将树抽象成树状数组,然后以和根节点的层数关系作为d,开两个树状数组分别计算添加值和减少值。
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 200005;
struct state {
int l, r, v, d;
}node[N];
int n, m, cnt, bit[2][N*2];
vector<int> g[N];
void add (int x, int val, int *b) {
while (x <= n * 2) {
b[x] += val;
x += (x & (-x));
}
}
int get(int x, int *b) {
int ans = 0;
while (x > 0) {
ans += b[x];
x -= (x & (-x));
}
return ans;
}
void dfs(int c, int fa, int d) {
node[c].l = cnt++; node[c].d = d;
for (int i = 0; i < g[c].size(); i++) {
if (g[c][i] == fa) continue;
dfs(g[c][i], c, 1 - d);
}
node[c].r = cnt++;
}
void init () {
cnt = 1;
scanf("%d%d", &n, &m);
memset(bit, 0, sizeof(bit));
for (int i = 1; i <= n; i++) scanf("%d", &node[i].v);
int a, b;
for (int i = 1; i < n; i++) {
scanf("%d%d", &a, &b);
g[a].push_back(b);
g[b].push_back(a);
}
dfs(1, -1, 0);
}
void solve () {
int o, a, b;
for (int i = 0; i < m; i++) {
scanf("%d", &o);
if (o == 1) {
scanf("%d%d", &a, &b);
add(node[a].l, b, bit[node[a].d]);
add(node[a].r + 1, -b, bit[node[a].d]);
} else {
scanf("%d", &a);
printf("%d\n", node[a].v + get(node[a].l, bit[node[a].d]) - get(node[a].l, bit[1 - node[a].d]));
}
}
}
int main () {
init ();
solve ();
return 0;
}
分享到:
相关推荐
Codeforces 题库 101-200 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
打codeforces的神器
codeforces编程网站预测分数插件
Codeforces 题库 001-100 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
编码 C ++中的Codeforce问题的解决方案
暴枚最长桌脚的长度$l$,然后长度比$l$长的桌脚全部都要砍掉长度比$l$短的桌脚选择代价前$k$小的砍掉用线段树维护;示例程序 :typedef long l
使用于Google Chrome的Codeforces Enhancer 1.1.2插件安装包。 版本:codeforces enhancer 1.1.2 使用浏览器:Google Chrome
回头重新看了一下题意,这不就是求最长链的树形dp裸题吗? 代码如下: #include #define ll long long #define inf 0x3f3f3f3f #define mod 1000000007 #define PI acos(-1) #define fi first #define se second #...
Codeforces 185A - Plant 全测试点49个
E. Tree Queries time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output You are given a rooted tree consisting of
codeforces 19 E Fairy 一道比较难的题目的解题报告 推荐阅读
Codeforces global round 10 codes
Codeforces round 678 division 2 codes
Some of the Codeforces problems codes
一个Codeforces、牛客竞赛、AtCoder平台的编程竞赛查询插件,ACMer必备.zip
Codeforces - 1107B. Digital root & 1107C. Brutality(规律 & 贪心)Codeforces - 1107B.
Codeforces round 678 D2_Codeforces_源码
lucifer1004大佬的博客cf上分攻略故里大佬的githubcf思维题刷题数:44- (1421)codeforces 676 div2 A,B done
codeforces-js Codeforces JS
Codeforces Round #723 (Div. 2).md