正文
SPOJ QTREE3 lct
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
题目链接
题意：
给定n个点 q个询问
以下n-1行给出树边，点有黑或白色。初始化为白色
以下q行：
询问有2种：
1、 0 x 把x点黑变白，白变黑
2、1 x 询问Path(1,x)路径上第一个黑点的点标， 若不存在黑点则输出-1
思路：
lct裸题
#include <iostream>
#include <fstream>
#include <string>
#include <time.h>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <stack>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
using namespace std;
template <class T>
inline bool rd(T &ret) {
char c; int sgn;
if (c = getchar(), c == EOF) return 0;
while (c != '-' && (c<'0' || c>'9')) c = getchar();
sgn = (c == '-') ? -1 : 1;
ret = (c == '-') ? 0 : (c - '0');
while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c - '0');
ret *= sgn;
return 1;
}
template <class T>
inline void pt(T x) {
if (x <0) {
putchar('-');
x = -x;
}
if (x>9) pt(x / 10);
putchar(x % 10 + '0');
}
typedef long long ll;
typedef pair<int, int> pii;
const int N = 30005;
const int inf = 10000000;
struct Node *null;
struct Node{
Node *fa, *ch[2];
int size;
int val, ma, sum, id;
bool rev;
inline void put(){
printf("%d:id, %d,%d,%d (%d,%d) fa:%d \n", id, val, ma, sum, ch[0]->id, ch[1]->id, fa->id);
}
inline void clear(int _val, int _id){
fa = ch[0] = ch[1] = null;
size = 1;
rev = 0;
id = _id;
val = ma = sum = _val;
}
inline void push_up(){
size = 1 + ch[0]->size + ch[1]->size; sum = ma = val;
if (ch[0] != null) {
sum += ch[0]->sum;
ma = max(ma, ch[0]->ma);
}
if (ch[1] != null){
sum += ch[1]->sum;
ma = max(ma, ch[1]->ma);
}
}
inline void push_down(){
if (rev){
ch[0]->flip();
ch[1]->flip();
rev = 0;
}
}
inline void setc(Node *p, int d){
ch[d] = p;
p->fa = this;
}
inline bool d(){
return fa->ch[1] == this;
}
inline bool isroot(){
return fa == null || fa->ch[0] != this && fa->ch[1] != this;
}
inline void flip(){
if (this == null)return;
swap(ch[0], ch[1]);
rev ^= 1;
}
inline void go(){//从链头開始更新到this
if (!isroot())fa->go();
push_down();
}
inline void rot(){
Node *f = fa, *ff = fa->fa;
int c = d(), cc = fa->d();
f->setc(ch[!c], c);
this->setc(f, !c);
if (ff->ch[cc] == f)ff->setc(this, cc);
else this->fa = ff;
f->push_up();
}
inline Node*splay(){
go();
while (!isroot()){
if (!fa->isroot())
d() == fa->d() ? fa->rot() : rot();
rot();
}
push_up();
return this;
}
inline Node* access(){//access后this就是到根的一条splay，而且this已经是这个splay的根了
for (Node *p = this, *q = null; p != null; q = p, p = p->fa){
p->splay()->setc(q, 1);
p->push_up();
}
return splay();
}
inline Node* find_root(){
Node *x;
for (x = access(); x->push_down(), x->ch[0] != null; x = x->ch[0]);
return x;
}
void make_root(){
access()->flip();
}
void cut(){//把这个点的子树脱离出去
access();
ch[0]->fa = null;
ch[0] = null;
push_up();
}
void cut(Node *x){
if (this == x || find_root() != x->find_root())return;
else {
x->make_root();
cut();
}
}
void link(Node *x){
if (find_root() == x->find_root())return;
else {
make_root(); fa = x;
}
}
};
Node pool[N], *tail;
Node *node[N];
int n, q;
void debug(Node *x){
if (x == null)return;
x->put();
debug(x->ch[0]);
debug(x->ch[1]);
}
inline void change(Node* x){
x->access();
x->val ^= 1;
x->push_up();
}
inline int ask(Node* x){
node[1]->make_root();
x->access();
node[1]->splay();
// for (int i = 1; i <= n; i++)debug(node[i]), putchar('\n');
Node *r = node[1];
if (r->sum == 0)return -1;
while (true){
if (r->ch[0]->sum == 0 && r->val)return r->id;
r = r->ch[r->ch[0]->sum==0];
}
}
struct Edge{
int from, to, nex;
}edge[N << 1];
int head[N], edgenum;
void add(int u, int v){
Edge E = { u, v, head[u] };
edge[edgenum] = E;
head[u] = edgenum++;
}
void dfs(int u, int fa){
for (int i = head[u]; ~i; i = edge[i].nex){
int v = edge[i].to; if (v == fa)continue;
dfs(v, u);
node[v]->push_up();
node[v]->fa = node[u];
}
}
int main(){
while (cin>>n>>q){
memset(head, -1, sizeof head); edgenum = 0;
tail = pool;
null = tail++; null->clear(0, 0);
null->size = 0; null->sum = 0;
for (int i = 1; i <= n; i++) {
node[i] = tail++;
node[i]->clear(0, i);
}
for (int i = 1, u, v; i < n; i++){
rd(u); rd(v);
add(u, v); add(v, u);
}
dfs(1, 1);
int u, v;
while (q--){
rd(u); rd(v);
if (u == 0)change(node[v]);
else pt(ask(node[v])), putchar('\n');
}
}
return 0;
}
/*
9 8
1 2
1 3
2 4
2 9
5 9
7 9
8 9
6 8 1 3
0 8
1 6
1 7
0 2
1 9
0 2
1 9
*/
