hdu 3966 Aragorn 's Story (나무 사슬 분할 + 나무 모양 배열)
제목: 나무 한 그루 를 정 하고 세 가지 조작
Q x: 노드 x 의 값 조회 I x y w: 노드 x 에서 y 까지 이 경로 의 모든 노드 의 값 증가 w D x y w: 노드 x 에서 y 까지 이 경로 의 모든 노드 의 값 감소 w 문제 풀이 방향: 나무 사슬 로 나 누고 나무 모양 배열 로 모든 노드 의 값 을 유지 합 니 다.
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include
#include
#include
#include
using namespace std;
#define lowbit(x) ((x)&(-x))
const int maxn = 50000;
int N, M, Q, val[maxn+5], fenw[maxn+5];
vector<int> g[maxn+5];
inline void add (int x, int v) {
while (x <= N) {
fenw[x] += v;
x += lowbit(x);
}
}
inline void add (int l, int r, int v) {
add(l, v);
add(r+1, -v);
}
inline int query (int x) {
int ret = 0;
while (x) {
ret += fenw[x];
x -= lowbit(x);
}
return ret;
}
int id, far[maxn+5], son[maxn+5], dep[maxn+5], cnt[maxn+5], top[maxn+5], idx[maxn+5];
void dfs_fir(int u, int pre, int d) {
dep[u] = d;
cnt[u] = 1;
son[u] = 0;
far[u] = pre;
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i];
if (v == pre)
continue;
dfs_fir(v, u, d + 1);
cnt[u] += cnt[v];
if (cnt[son[u]] < cnt[v])
son[u] = v;
}
}
void dfs_sec(int u, int rot) {
idx[u] = id++;
top[u] = rot;
if (son[u])
dfs_sec(son[u], rot);
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i];
if (v == son[u] || v == far[u])
continue;
dfs_sec(v, v);
}
}
void change (int u, int v, int c) {
int p = top[u], q = top[v];
while (p != q) {
if (dep[p] < dep[q]) {
swap(p, q);
swap(u, v);
}
add(idx[p], idx[u], c);
u = far[p];
p = top[u];
}
/*
if (dep[u] > dep[v]) swap(u, v);
add(idx[u], idx[v], c);
*/
if (dep[u] < dep[v]) swap(u, v);
add(idx[v], idx[u], c);
}
int main () {
while (scanf("%d%d%d", &N, &M, &Q) == 3) {
id = 1;
memset(fenw, 0, sizeof(fenw));
for (int i = 1; i <= N; i++) {
scanf("%d", &val[i]);
g[i].clear();
}
int u, v, c;
for (int i = 0; i < M; i++) {
scanf("%d%d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
}
dfs_fir(1, -1, 0);
dfs_sec(1, 1);
for (int i = 1; i <= N; i++) add(idx[i], idx[i], val[i]);
char op[5];
while (Q--) {
scanf("%s%d", op, &u);
if (op[0] == 'Q')
printf("%d
", query(idx[u]));
else {
scanf("%d%d", &v, &c);
if (op[0] == 'D') c = -c;
change(u, v, c);
}
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
hdu 3966 Aragorn 's Story (나무 사슬 분할 + 나무 모양 배열)제목 링크: hdu 3966 Aragorn 's Story 제목: 나무 한 그루 를 정 하고 세 가지 조작 Q x: 노드 x 의 값 조회 I x y w: 노드 x 에서 y 까지 이 경로 의 모든 노드 의 값 증가 w...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.