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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.