(color{#0066ff}{ 题目描述 })
-
计算神经学作为新兴的交叉学科近些年来一直是学术界的热点。一种叫做SHOI 的神经组织因为其和近日发现的化合物 SHTSC 的密切联系引起了人们的极大关注。
SHOI 组织由若干个 SHOI 细胞构成,SHOI 细胞之间形成严密的树形结构。每个 SHOI 细胞都有且只有一个输出端,被称为轴突,除了一个特殊的、被称为根细胞的 SHOI 细胞的输出作为整个组织的输出以外,其余细胞的轴突均连向其上级 SHOI 细胞；并且有且只有三个接收端,被称为树突,从其下级细胞或者其它神经组织那里接收信息。SHOI 细胞的信号机制较为简单,仅有 (0)和 (1)两种。每个 SHOI 细胞根据三个输入端中 (0)和 (1)信号的多寡输出较多的那一种。
现在给出了一段 SHOI 组织的信息,以及外部神经组织的输入变化情况。请你模拟 SHOI 组织的输出结果。
(color{#0066ff}{输入格式})
-
输入的第一行包含一个整数 (n)。表示 SHOI 组织的总细胞个数。SHOI 细胞由 (1)~ (n) 编号,编号为 (1) 的是根细胞。
从第二行开始的 (n)行,每行三个整数 (x_1, x_2, x_3),分别表示编号为 (1)~ (n) 的 SHOI 细胞的树突连接。(1 < x_i leq n) 表示连向编号为 (x_i) 的细胞的轴突, (n < x_i leq 3n+1) 表示连向编号为 (x_i) 的外界输入。输入数据保证给出的 SHOI 组织是合法的，且所有的 (x_i) 两两不同。
接下来一行包含 (2n+1) 个 (0/1) 的整数,表示初始时的外界输入。
第 (n+3)行有一个整数 (q),表示总操作数。
之后 (q) 行每行一个整数 (x),表示编号为 (x) 的外界输入发生了变化。
(color{#0066ff}{输出格式})
输出 (q) 行，每行一个整数,对应第 (i) 次外界输入变化后的根细胞的输出。
(color{#0066ff}{输入样例})
3
2 3 4
5 6 7
8 9 10
0 0 0 0 1 1 1
5
4
4
5
6
8
(color{#0066ff}{输出样例})
1
0
0
1
1
(color{#0066ff}{数据范围与提示})
对于 (10 \%)的数据， (n leq 1000, q leq 1000)。
对于 (30 \%)的数据， (n leq 100000, q leq 100000)。
对于 (100 \%)的数据， (n leq 500000, q leq 500000)。
(color{#0066ff}{ 题解 })
这毒瘤题读了半天没看懂啥意思，现在简单概括一下题意
给你一颗三叉树（类比二叉树qwq），1为根，前n个点每个点有三个孩子，(n+1 o3n)这些点为叶子节点，然后给你所有叶子的权值0/1，定义(1-n)点的权值为，三个孩子中权为1的孩子的个数是否大于1，如果是则权值为1，否则为0。现在给你一些操作，每次让一个叶子的权值异或1，每次操作输出根的权值
我们考虑每次操作对答案的影响，设(v_i)为i有多少个权值为1的孩子(v_iin [0,3])
如果当前点权值由0变1，那么什么情况下父亲的权值也会改变呢
显然当且仅当父亲的v=1，那么加上自己的改变， 父亲的v变为2，这时父亲的权值也从原来的0变为1，这就是一个子问题了
同理，如果是1变0， 当且仅当父亲的v=2时父亲也会改变
那么，我们可以得到一个结论，每次修改一个点产生的影响是从这个点向上一条连续v为1或2的链的权值的改变，只要这个链包括了1， 答案就会改变
那么现在的问题是，怎么快速维护这个东西，我们需要快速找到一个点向上延伸1/2的最上面那个点，还有一条链的权值的修改
可以用LCT维护这个东西， 显然不需要makeroot操作，那么翻转标记就没用了
每个点维护两个点的指针，一个是最深的v!=1的点，一个是最深的v!=2的点
这个点实际上就是延伸的链顶的父亲
为什么要最深？ 因为要保证下面的1/2连续
怎么维护？ 因为要最深，所以在splay上，先考虑右儿子，然后是自己，最后是左儿子
如果这个点存在，那么就对答案没有影响（仔细想想），我们把这个点转上去，那么实际上就是当前点的单点修改，右子树整体的修改，这个打标记即可，注意v改变了，n1和n2要互换！
如果不存在呢，说明此链一直延伸到根，那么直接对整个splay打标记，并把答案修改即可
这题就没了。。。
发现实际上每个点的权值就是(frac v 2)，所以直接维护v就行了
#include<bits/stdc++.h>
#define LL long long
LL in() {
char ch; LL x = 0, f = 1;
while(!isdigit(ch = getchar()))(ch == '-') && (f = -f);
for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 1) + (x << 3) + (ch ^ 48));
return x * f;
}
const int maxn = 5e5 + 3;
const int maxm = 1.5e6 + 3;
struct node {
node *ch[2], *fa, *n1, *n2;
int val, tag;
node(int val = 0, int tag = 0): val(val), tag(tag) {
ch[0] = ch[1] = fa = n1 = n2 = NULL;
}
void trn() { std::swap(n1, n2); val ^= 3; tag ^= 1; }
void dwn() {
if(!tag) return;
if(ch[0]) ch[0]->trn();
if(ch[1]) ch[1]->trn();
tag = 0;
}
void upd() {
n1 = n2 = NULL; //这行不能少！
//右根左这样找
if(ch[1]) n1 = ch[1]->n1;
if(!n1) n1 = this->val == 1? NULL : this;
if(ch[0] && !n1) n1 = ch[0]->n1;
if(ch[1]) n2 = ch[1]->n2;
if(!n2) n2 = this->val == 2? NULL : this;
if(ch[0] && !n2) n2 = ch[0]->n2;
}
bool isr() { return this == fa->ch[1]; }
bool ntr() { return fa && (fa->ch[1] == this || fa->ch[0] == this); }
}pool[maxn];
int fa[maxm], val[maxm], du[maxm];
int n, ans;
void toposort() {
std::queue<int> q;
for(int i = n + 1; i <= 3 * n + 1; i++) val[i] = in() << 1, q.push(i);
while(!q.empty()) {
int tp = q.front(); q.pop();
if(tp <= n) pool[tp].upd(), pool[tp].fa = pool + fa[tp];
pool[fa[tp]].val += (tp > n? val[tp] : pool[tp].val) >> 1;
du[fa[tp]]--;
if(!du[fa[tp]]) q.push(fa[tp]);
}
pool[1].fa = NULL;
}
void rot(node *x) {
node *y = x->fa, *z = y->fa;
bool k = x->isr(); node *w = x->ch[!k];
if(y->ntr()) z->ch[y->isr()] = x;
(x->ch[!k] = y)->ch[k] = w;
(y->fa = x)->fa = z;
if(w) w->fa = y;
y->upd(), x->upd();
}
void splay(node *o) {
static node *st[maxn];
int top;
st[top = 1] = o;
while(st[top]->ntr()) st[top + 1] = st[top]->fa, top++;
while(top) st[top--]->dwn();
while(o->ntr()) {
if(o->fa->ntr()) rot(o->isr() ^ o->fa->isr()? o : o->fa);
rot(o);
}
}
void access(node *x) {
for(node *y = NULL; x; x = (y = x)->fa)
splay(x), x->ch[1] = y, x->upd();
}
int main() {
n = in();
for(int i = 1; i <= n; i++) du[fa[in()] = fa[in()] = fa[in()] = i] = 3;
toposort();//求初始的答案
ans = pool[1].val >> 1;
int x, tp;
for(int T = in(); T --> 0;) {
tp = (val[x = in()] ^= 2) >> 1;
access(pool + (x = fa[x])), splay(pool + x);
node *o = pool + x;
node *nr = tp? o->n1 : o->n2; //找最深的点
if(nr) {
splay(nr);
if(nr->ch[1]) nr->ch[1]->trn(), nr->ch[1]->upd();
nr->val += tp? 1 : -1;
nr->upd();
}
else ans ^= 1, o->trn(), o->upd();
printf("%d
", ans);
}
return 0;
}