P1501 [국가대표 소집팀] Tree II LCT
링크
luogu
사고의 방향
간단한 문제
코드
#include
#define ls c[x][0]
#define rs c[x][1]
using namespace std;
const int N = 1e5 + 7, mod = 51061;
int read() {
int x = 0, f = 1; char s = getchar();
for (;s > '9' || s < '0'; s = getchar()) if (s == '-') f = -1;
for (;s >= '0' && s <= '9'; s = getchar()) x = x * 10 + s - '0';
return x * f;
}
int f[N], c[N][2], w[N], siz[N], lazy[N], stak[N];
int add[N], mul[N], sum[N];
bool isroot(int x) {return c[f[x]][0] == x || c[f[x]][1] == x;}
void tag(int x) {swap(ls, rs), lazy[x] ^= 1;}
void tag1(int x, int ad) {
add[x] = (add[x] + ad) % mod;
sum[x] = (sum[x] + 1LL * ad * siz[x] % mod) % mod;
w[x] = (w[x] + ad) % mod;
}
void tag2(int x, int mu) {
mul[x] = 1LL * mul[x] * mu % mod;
add[x] = 1LL * add[x] * mu % mod;
sum[x] = 1LL * sum[x] * mu % mod;
w[x] = 1LL * w[x] * mu % mod;
}
void pushup(int x) {
sum[x] = (sum[ls] + sum[rs] + w[x]) % mod;
siz[x] = siz[ls] + siz[rs] + 1;
}
void pushdown(int x) {
if (lazy[x]) {
if (ls) tag(ls);
if (rs) tag(rs);
lazy[x] ^= 1;
}
if (mul[x] != 1) {
if (ls) tag2(ls, mul[x]);
if (rs) tag2(rs, mul[x]);
mul[x] = 1;
}
if (add[x]) {
if (ls) tag1(ls, add[x]);
if (rs) tag1(rs, add[x]);
add[x] = 0;
}
}
void rotate(int x) {
int y = f[x], z = f[y], k = c[y][1] == x, w = c[x][!k];
if (isroot(y)) c[z][c[z][1] == y] = x;
c[x][!k] = y;
c[y][k] = w;
if (w) f[w] = y;
f[x] = z;
f[y] = x;
pushup(y);
}
void splay(int x) {
int y = x, z = 0;
stak[++z] = y;
while (isroot(y)) stak[++z] = y = f[y];
while (z) pushdown(stak[z--]);
while (isroot(x)) {
y = f[x], z = f[y];
if (isroot(y)) rotate((c[y][0] == x)^(c[z][0] == y) ? x : y);
rotate(x);
}
pushup(x);
}
void access(int x) {
for (int y = 0; x;x = f[y = x])
splay(x), rs = y, pushup(x);
}
void makeroot(int x) {
access(x), splay(x), tag(x);
}
int findroot(int x) {
access(x), splay(x);
while(ls) pushdown(x), x = ls;
return x;
}
void split(int x, int y) {
makeroot(x), access(y), splay(y);
}
void link(int x, int y) {
makeroot(x);
if (findroot(y) != x) f[x] = y;
}
void cut(int x, int y) {
makeroot(x);
if (findroot(y) == x && f[x] == y && !rs) {
f[x] = c[y][0] = 0;
pushup(y);
}
}
int main() {
int n = read(), q = read();
for (int i = 1; i <= n; ++i) w[i] = mul[i] = 1;
for (int i = 1; i < n; ++i) {
int u = read(), v = read();
link(u, v);
}
char s[10];
for (int i = 1; i <= q; ++i) {
scanf("%s", s);
if (s[0] == '+') {
int u = read(), v = read(), c = read();
split(u, v), tag1(v, c);
}
if (s[0] == '-') {
int u = read(), v = read(), u1 = read(), v1 = read();
cut(u, v),link(u1, v1);
}
if (s[0] == '*') {
int u = read(), v = read(), c = read();
split(u, v), tag2(v, c);
}
if (s[0] == '/') {
int u = read(), v = read();
split(u, v), printf("%d
", sum[v]);
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.