제목:
나무 한 그루 삭제 변 추가, 경로 가중치 추가, 경로 가중치 변경, 경로 에서 두 번 째 로 큰 숫자 와 개 수 를 구 하 는 것 을 지원 합 니 다.
생각:
엘 시 티 의 두 번 째 문제. 제목 의 뜻 은 이미 기능 을 모두 알려 주 었 다. 비교적 나체로
주의해 야 할 것 은 가중치 와 값 변경 두 작업 의 태그 아래 문제 입 니 다. 먼저 다운 하여 값 을 바 꿔 야 한다. 더 다운 플러스
경로 에 대한 조작 은 mroot 를 통 해 트 리 의 형 태 를 바 꾸 고 access 에서 경 로 를 꺼 내 는 것 이 편리 합 니 다. 나 전편 처럼 lca 하지 마.
코드:
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define N 100010
#define L(x) (ch[x][0])
#define R(x) (ch[x][1])
#define inf -2147483640
int ch[N][2], pre[N], rev[N], me[N];
int cov[N], add[N], size[N], max1[N], num1[N], max2[N], num2[N];
bool rt[N];
struct helper {
int val, num;
bool operator ff.val;
}
} hel[10];
void Update_COV(int u, int d) {
if (!u)
return;
me[u] = d;
cov[u] = d;
add[u] = inf;
max1[u] = d;
num1[u] = size[u];
max2[u] = inf;
num2[u] = 0;
}
void Update_Add(int u, int d) {
if (!u)
return;
me[u] += d;
if (add[u] != inf)
add[u] += d;
else
add[u] = d;
max1[u] += d;
if (max2[u] != inf)
max2[u] += d;
}
void Update_Rev(int u) {
if (!u)
return;
swap(L(u), R(u));
rev[u] ^= 1;
}
void down(int u) {
if (rev[u]) {
Update_Rev(L(u));
Update_Rev(R(u));
rev[u] = 0;
}
if (cov[u] != inf) {
Update_COV(L(u), cov[u]);
Update_COV(R(u), cov[u]);
cov[u] = inf;
}
if (add[u] != inf) {
Update_Add(L(u), add[u]);
Update_Add(R(u), add[u]);
add[u] = inf;
}
}
void up(int u) {
size[u] = size[L(u)] + size[R(u)] + 1;
hel[0].val = max1[L(u)];
hel[0].num = num1[L(u)];
hel[1].val = max2[L(u)];
hel[1].num = num2[L(u)];
hel[2].val = max1[R(u)];
hel[2].num = num1[R(u)];
hel[3].val = max2[R(u)];
hel[3].num = num2[R(u)];
hel[4].val = me[u];
hel[4].num = 1;
sort(hel, hel + 5);
int i;
for (i = 1; i < 5; i++) {
if (hel[i].val != hel[i - 1].val)
break;
}
max1[u] = hel[0].val;
max2[u] = hel[i].val;
num1[u] = num2[u] = 0;
for (i = 0; i < 5; i++) {
if (hel[i].val == max1[u])
num1[u] += hel[i].num;
else if (hel[i].val == max2[u])
num2[u] += hel[i].num;
}
}
//Rotate P Splay
void Rotate(int x) {
int y = pre[x], kind = ch[y][1] == x;
ch[y][kind] = ch[x][!kind];
pre[ch[y][kind]] = y;
pre[x] = pre[y];
pre[y] = x;
ch[x][!kind] = y;
if (rt[y])
rt[y] = false, rt[x] = true;
else
ch[pre[x]][ch[pre[x]][1] == y] = x;
up(y);
}
//P splay u
void P(int u) {
if (!rt[u])
P(pre[u]);
down(u);
}
void Splay(int u) {
P(u);
while (!rt[u]) {
int fa = pre[u], ffa = pre[fa];
if (rt[fa])
Rotate(u);
else if ((R(ffa) == fa) == (R(fa) == u))
Rotate(fa), Rotate(u);
else
Rotate(u), Rotate(u);
}
up(u);
}
// root u
int Access(int u) {
int v = 0;
for (; u; u = pre[v = u]) {
Splay(u);
rt[R(u)] = true, rt[R(u) = v] = false;
up(u);
}
return v;
}
// u
void mroot(int u) {
Access(u);
Splay(u);
Update_Rev(u);
}
// u v
void link(int u, int v) {
mroot(u);
pre[u] = v;
}
//u-v
void cut(int u, int v) {
mroot(u);
Access(u);
Splay(v);
pre[L(v)] = pre[v];
pre[v] = 0;
rt[L(v)] = true;
L(v) = 0;
up(v);
}
//u-v w
void COV(int u, int v, int w) {
mroot(u);
Access(v);
Splay(v);
Update_COV(v, w);
}
//u-v +w
void ADD(int u, int v, int w) {
mroot(u);
Access(v);
Splay(v);
Update_Add(v, w);
}
//u-v
void query(int u, int v) {
mroot(u);
Access(v);
Splay(v);
if (max2[v] != inf)
printf("%d %d
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[HDU] 4089 활성화 확률 DP
dp[i][j]를 모두 i개인의 대기열인 Tomato가 j위 서버가 마비될 확률로 역추를 사용하면 우리는 상태 이동 방정식을 얻을 수 있다.
i == 1 : dp[1][1] = dp[1][1] * p1 + dp[1]...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
