HYSBZ - 1036 나무의 통계

사고: 이것 은 전형 적 인 나무 사슬 로 나 뉘 는데 세 가지 조작 이 있 습 니 다.
1. 두 가지 경로 중의 최대 점 권;
2. 두 가지 경로 중의 점 권 과;
3. 특정한 점 의 가중치 변경;
데이터 구 조 를 유지 하지 않 으 면 직접 검색 하 는 것 은 시간 소모 가 너무 크다 는 것 이다. 주로 검색 하 는 과정 에서 많은 공 을 들 이지 않 고 목표 점 과 라인 을 직접적 으로 찾 지 못 했 기 때문이다.나 무 를 자 르 는 것 은 먼저 아들 노드 수의 노드 에 따라 위험 구간 을 나 누 는 것 이다. 선분 이 교차 하지 않 고 나무 위의 두 점 의 경 로 는 반드시 그들의 LCA 를 통과 할 것 이다.우 리 는 라인 을 통 해 위로 찾 을 수 있 고 두 점 이 같은 라인 에 있다 는 것 을 알 수 있 습 니 다. 그러면 우 리 는 세그먼트 의 업데이트 값 이 될 수 있 습 니 다.
/*****************************************
Author      :Crazy_AC(JamesQi)
Time        :2016
File Name   :
*****************************************/
// #pragma comment(linker, "/STACK:1024000000,1024000000")
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <sstream>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <map>
#include <set>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <climits>
using namespace std;
#define MEM(x,y) memset(x, y,sizeof x)
#define pk push_back
#define lson rt << 1
#define rson rt << 1 | 1
#define bug cout << "BUG HERE
" typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> ii; typedef pair<ii,int> iii; const double eps = 1e-10; const int inf = 1 << 30; const int INF = 0x3f3f3f3f; const int MOD = 1e9 + 7; int nCase = 0; const int maxn = 30100; int n, q; int a[maxn]; /*************************************************/ struct node { int l, r; int maxNum; LL sum; }p[maxn<<2]; int tmp[maxn]; void up(int rt) { p[rt].maxNum = max(p[lson].maxNum, p[rson].maxNum); p[rt].sum = p[lson].sum + p[rson].sum; } void build(int rt,int L, int R) { p[rt].l = L, p[rt].r = R; if (L == R) { p[rt].maxNum = p[rt].sum = tmp[L]; return ; } int mid = (L + R) >> 1; build(lson, L, mid); build(rson, mid + 1, R); up(rt); } void updata(int rt, int pos,int val) { if (p[rt].l == pos && p[rt].r == pos) { p[rt].sum = p[rt].maxNum = val; return ; } int mid = (p[rt].l + p[rt].r) >> 1; if (pos <= mid) updata(lson, pos, val); if (pos > mid) updata(rson, pos, val); up(rt); } LL QuerySum(int rt,int L, int R) { if (L <= p[rt].l && p[rt].r <= R) { return 1LL*p[rt].sum; } LL ret = 0LL; int mid = (p[rt].l + p[rt].r) >> 1; if (L <= mid) ret += QuerySum(lson, L, R); if (R > mid) ret += QuerySum(rson, L, R); return ret; } int QueryMax(int rt,int L, int R) { if (L <= p[rt].l && p[rt].r <= R) { return p[rt].maxNum; } int ans = -inf; int mid = (p[rt].l + p[rt].r) >> 1; if (L <= mid) ans = max(ans, QueryMax(lson, L, R)); if (R > mid) ans = max(ans, QueryMax(rson, L, R)); return ans; } /*************************************************/ vector<int> G[maxn]; int Times; int fa[maxn], top[maxn], size[maxn], son[maxn]; int SegId[maxn], TreeId[maxn]; int dep[maxn]; int dfs_first(int u,int pre,int depth) { fa[u] = pre, dep[u] = depth, size[u] = 1; int tmp = 0; for (int i = 0;i < G[u].size();++i) { int v = G[u][i]; if (v == pre) continue; int now = dfs_first(v, u, depth + 1); size[u] += now; if (now > tmp) { tmp = now; son[u] = v; } } return size[u]; } void dfs_second(int u,int header) { top[u] = header; if (son[u] != -1) { SegId[u] = ++Times; TreeId[Times] = u; dfs_second(son[u], header); }else if (son[u] == -1) { SegId[u] = ++Times; TreeId[Times] = u; return ; } for (int i = 0;i < G[u].size();++i) { int v = G[u][i]; if (v == fa[u] || v == son[u]) continue; dfs_second(v, v); } } /*************************************************/ int findmax(int u,int v) { int ans = -inf; int p = top[u], q = top[v]; while(p != q) { if (dep[p] < dep[q]) { swap(u, v); swap(p, q); } ans = max(ans, QueryMax(1,SegId[p], SegId[u])); u = fa[p]; p = top[u]; } if (dep[u] < dep[v]) swap(u, v); ans = max(ans, QueryMax(1, SegId[v], SegId[u])); return ans; } LL findsum(int u,int v) { int p = top[u], q = top[v]; LL sum = 0LL; while(p != q) { if (dep[p] < dep[q]) { swap(u, v); swap(p, q); } sum += QuerySum(1, SegId[p], SegId[u]); u = fa[p]; p = top[u]; } if (dep[u] < dep[v]) swap(u, v); sum += QuerySum(1, SegId[v], SegId[u]); return sum; } void change(int u,int val) { updata(1, SegId[u], val); } /*************************************************/ int main(int argc, const char * argv[]) { // freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); while(~scanf("%d",&n)) { for (int i = 1;i <= n;++i) G[i].clear(); int u, v; for (int i = 1;i < n;++i) { scanf("%d%d",&u,&v); G[u].push_back(v); G[v].push_back(u); } memset(son, -1, sizeof son); Times = 0; for (int i = 1;i <= n;++i) scanf("%d", &a[i]); // dfs_first(1, -1, 0); dfs_second(1, 1); for (int i = 1;i <= n;++i) { tmp[ SegId[i] ] = a[i]; } // build(1, 1, n); scanf("%d",&q); char op[10]; while(q--) { scanf("%s", op); if (strcmp(op, "QMAX") == 0) { scanf("%d%d",&u,&v); printf("%d
", findmax(u, v)); } if (strcmp(op, "QSUM") == 0) { scanf("%d%d",&u,&v); printf("%lld
", findsum(u, v)); } if (strcmp(op, "CHANGE") == 0) { scanf("%d%d",&u,&v); change(u, v); } } } return 0; }

좋은 웹페이지 즐겨찾기