Codeforces Round \ # 225 (Div. 2) --- E. 전파 트 리 (타임 스탬프 + 선분 트 리)
18919 단어 데이터 구조codeforces
This tree has a special property: when a value val is added to a value of node i, the value -val is added to values of all the children of node i. Note that when you add value -val to a child of node i, you also add -(-val) to all children of the child of node i and so on. Look an example explanation to understand better how it works.
This tree supports two types of queries:
"1 x val" — val is added to the value of node x;
"2 x" — print the current value of node x.
In order to help Iahub understand the tree better, you must answer m queries of the preceding type. Input
The first line contains two integers n and m (1 ≤ n, m ≤ 200000). The second line contains n integers a1, a2, …, an (1 ≤ ai ≤ 1000). Each of the next n–1 lines contains two integers vi and ui (1 ≤ vi, ui ≤ n), meaning that there is an edge between nodes vi and ui.
Each of the next m lines contains a query in the format described above. It is guaranteed that the following constraints hold for all queries: 1 ≤ x ≤ n, 1 ≤ val ≤ 1000. Output
For each query of type two (print the value of node x) you must print the answer to the query on a separate line. The queries must be answered in the order given in the input. Sample test(s) Input
5 5 1 2 1 1 2 1 2 1 3 2 4 2 5 1 2 3 1 1 2 2 1 2 2 2 4
Output
3 3 0
Note
The values of the nodes are [1, 2, 1, 1, 2] at the beginning.
Then value 3 is added to node 2. It propagates and value -3 is added to it’s sons, node 4 and node 5. Then it cannot propagate any more. So the values of the nodes are [1, 5, 1, - 2, - 1].
Then value 2 is added to node 1. It propagates and value -2 is added to it’s sons, node 2 and node 3. From node 2 it propagates again, adding value 2 to it’s sons, node 4 and node 5. Node 3 has no sons, so it cannot propagate from there. The values of the nodes are [3, 3, - 1, 0, 1].
You can see all the definitions about the tree at the following link: http://en.wikipedia.org/wiki/Tree_(graph_theory)
dfs 를 먼저 달 려 서 시간 도장 을 받 아야 하 는 것 이 분명 합 니 다. 그러나 이것 이 부족 합 니 다. 여기 서 특정한 노드 에 어떤 숫자 를 더 한 후에 그의 아들 은 그 수 를 빼 야 합 니 다. 그의 아들 의 아들 은 그 수 를 더 해 야 합 니 다. 그래서 우 리 는 깊이 의 인형 에 따라 시간 도장 을 2 개의 배열 로 만 들 고 2 개의 선분 나 무 를 만들어 야 합 니 다.
/*************************************************************************
> File Name: CF225-E.cpp
> Author: ALex
> Mail: [email protected]
> Created Time: 2015 04 21 21 11 04
************************************************************************/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const double eps = 1e-15;
typedef long long LL;
typedef pair <int, int> PLL;
static const int N = 300010;
int par[N];
int oddL[N];
int oddR[N];
int evenL[N];
int evenR[N];
int subL[N];
int subR[N];
int dep[N];
int arr[N];
int now[N];
int sta[N];
int is_leaf[N];
struct node{
int add;
int l, r;
int sum;
}tree[2][N << 2];
struct EDGE {
int to;
int nxt;
}edge[N << 1];
int head[N], tot;
void addedge(int from, int to) {
edge[tot].to = to;
edge[tot].nxt = head[from];
head[from] = tot++;
}
void build(node tree[], int p, int l, int r) {
tree[p].l = l;
tree[p].r = r;
tree[p].add = 0;
if (l == r) {
tree[p].sum = now[l];
return;
}
int mid = (l + r) >> 1;
build(tree, p << 1, l, mid);
build(tree, p << 1 | 1, mid + 1, r);
tree[p].sum = tree[p << 1].sum + tree[p << 1 | 1].sum;
}
void pushdown(node tree[], int p) {
if (tree[p].add) {
tree[p << 1].add += tree[p].add;
tree[p << 1 | 1].add += tree[p].add;
int m = tree[p << 1].r - tree[p << 1].l + 1;
tree[p << 1].sum += m * tree[p].add;
m = tree[p << 1 | 1].r - tree[p << 1 | 1].l + 1;
tree[p << 1 | 1].sum += m * tree[p].add;
tree[p].add = 0;
}
}
void update(node tree[], int p, int l, int r, int val) {
if (l == tree[p].l && r == tree[p].r) {
tree[p].add += val;
int m = r - l + 1;
tree[p].sum += m * val;
return;
}
pushdown(tree, p);
int mid = (tree[p].l + tree[p].r) >> 1;
if (r <= mid) {
update(tree, p << 1, l, r, val);
}
else if (l > mid) {
update(tree, p << 1 | 1, l, r, val);
}
else {
update(tree, p << 1, l, mid, val);
update(tree, p << 1 | 1, mid + 1, r, val);
}
tree[p].sum = tree[p << 1].sum + tree[p << 1 | 1].sum;
}
int query(node tree[], int p, int pos) {
if (tree[p].l == tree[p].r) {
return tree[p].sum;
}
pushdown(tree, p);
int mid = (tree[p].l + tree[p].r) >> 1;
if (pos <= mid) {
return query(tree, p << 1, pos);
}
else {
return query(tree, p << 1 | 1, pos);
}
}
void getDepth(int u, int fa, bool flag) { // 1 -> , 2 ->
par[u] = fa;
dep[u] = flag;
bool ok = 1;
for (int i = head[u]; ~i; i = edge[i].nxt) {
int v = edge[i].to;
if (v == fa) {
continue;
}
getDepth(v, u, flag ^ 1);
ok = 0;
}
is_leaf[u] = ok;
}
void dfs1(int u, int fa, int &ret) {
if (dep[u]) {
oddL[u] = ++ret;
}
for (int i = head[u]; ~i; i = edge[i].nxt) {
int v = edge[i].to;
if (v == fa) {
continue;
}
dfs1(v, u, ret);
}
if (dep[u]) {
oddR[u] = ret;
}
}
void dfs2(int u, int fa, int &ret) {
if (!dep[u]) {
evenL[u] = ++ret;
}
for (int i = head[u]; ~i; i = edge[i].nxt) {
int v = edge[i].to;
if (v == fa) {
continue;
}
dfs2(v, u, ret);
}
if (!dep[u]) {
evenR[u] = ret;
}
}
int main() {
int n, m;
while (~scanf("%d%d", &n, &m)) {
for (int i = 1; i <= n; ++i) {
scanf("%d", &arr[i]);
}
memset(head, -1, sizeof(head));
memset(is_leaf, 0, sizeof(is_leaf));
tot = 0;
int u, v;
for (int i = 1; i <= n - 1; ++i) {
scanf("%d%d", &u, &v);
addedge(u, v);
addedge(v, u);
}
int L1 = 0, L2 = 0;
getDepth(1, -1, 1);
dfs1(1, -1, L1);
dfs2(1, -1, L2); //
for (int i = 1; i <= n; ++i) {
subL[i] = inf;
subR[i] = -inf;
if (is_leaf[i]) {
continue;
}
for (int j = head[i]; ~j; j = edge[j].nxt) {
if (edge[j].to == par[i]) {
continue;
}
if (dep[i]) {
subL[i] = min(subL[i], evenL[edge[j].to]);
subR[i] = max(subR[i], evenR[edge[j].to]);
}
else {
subL[i] = min(subL[i], oddL[edge[j].to]);
subR[i] = max(subR[i], oddR[edge[j].to]);
}
}
}
for (int i = 1; i <= n; ++i) {
if (!dep[i]) { //
now[evenL[i]] = arr[i];
}
}
if (L2 >= 1) {
build(tree[0], 1, 1, L2);
}
for (int i = 1; i <= n; ++i) {
if (dep[i]) {
now[oddL[i]] = arr[i];
}
}
if (L1 >= 1) {
build(tree[1], 1, 1, L1);
}
int op, x, y;
while (m--) {
scanf("%d", &op);
if (op == 1) {
scanf("%d%d", &x, &y);
if (dep[x]) {
int l = oddL[x];
int r = oddR[x];
update(tree[1], 1, l, r, y);
if (!is_leaf[x]) {
l = subL[x];
r = subR[x];
update(tree[0], 1, l, r, -y);
}
}
else {
int l = evenL[x];
int r = evenR[x];
update(tree[0], 1, l, r, y);
if (!is_leaf[x]) {
l = subL[x];
r = subR[x];
update(tree[1], 1, l, r, -y);
}
}
}
else {
scanf("%d", &x);
if (dep[x]) {
printf("%d
", query(tree[1], 1, oddL[x]));
}
else {
printf("%d
", query(tree[0], 1, evenL[x]));
}
}
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.