BZOJ 3553: [Shoi2014]三叉神经树

Description

Input

Output

Sample Input

Sample Output

HINT

Solution

    定义col[x]为x点输出的信号，val[x]为x点的孩子节点输出的信号和，易知col[x]∈{0,1},val[x]∈{0,1,2,3}。

    由于每次修改操作只会改变该点到根的路径上的点，所以可以树剖 （当然lct也可以 xllend3半个小时就解决了 orz）

    将col=0的点称为白点，将col=1的点称为黑点。

    考虑将一个白点x变为黑点，只有val[x]=1时才会对val[fa[x]]产生影响，那么在线段树中维护从左边开始连续相同的数的个数、从右边开始连续相同的数的个数即可。将一个黑点变白点也一样操作。

    修改只有将一段数加一或减一，加个标记即可。

Code

//+-------------------------------------+
//|     By   qwer_zcc                   |
//|     Date 18/05/2014                 |
//+-------------------------------------+
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#define INF 1000000000
#define LL long long
#define uLL unsigned long long
#define uint unsigned int
#define D double
#define LD long double
#define rep(i,a,b) for (int i=a;i<=b;i++)
#define dep(i,a,b) for (int i=a;i>=b;i--)
#define M(a) memset(a,0,sizeof(a));
#define Chen(a,b,c) int((LL)(a)*(LL)(b)%(LL)(c))
#define pb push_back
#define mp make_pair
#define ins insert
#define ps push
#define Pi M_PI
using namespace std;
template<class T> inline T abs(T &a) {return a>0?a:-a;}
template<class T> inline T min(T &a,T &b) {return a<b?a:b;}
template<class T> inline T max(T &a,T &b) {return a>b?a:b;}
inline void read(int &x)
{
	char ch;
	while ((ch=getchar()) && !(ch>='0' && ch<='9'));x=ch-'0';
	while ((ch=getchar()) && (ch>='0' && ch<='9')) x=x*10+ch-'0';
}
struct point
{
	int x,y;
	point() {}
	point(int _x,int _y) : x(_x),y(_y) {}
} ;
const int N=2100000;
vector<int>E[N];
int dep[N],size[N],n,val[N],col[N],dfn[N],ti,An[N],dy[N],nn,f[N][2];
void add(int x,int y){E[x].pb(y);}
void dfs(int x,int Fa)
{
    f[x][0]=Fa;if (x>nn) return;
	size[x]=1;
    int gs=0;
    for (int i=0;i<E[x].size();i++)
    if (E[x][i]!=Fa)
	{
		dfs(E[x][i],x);
		val[x]+=col[E[x][i]];
		if (col[E[x][i]]) gs++;
		size[x]+=size[E[x][i]];
	}
	if (gs>1) col[x]=1;
	else col[x]=0;
}
void Dfs(int x,int Fa,int c)
{
	if (x>nn) return;
    dfn[x]=++ti;An[x]=c;dy[ti]=x;
    int Max=0,il=0;
    for (int i=0;i<E[x].size();i++)
    if (E[x][i]!=Fa) if (size[E[x][i]]>Max) Max=size[E[x][i]],il=E[x][i];
    if (il) Dfs(il,x,c);
    for (int i=0;i<E[x].size();i++)
    if (E[x][i]!=Fa && E[x][i]!=il) Dfs(E[x][i],x,E[x][i]);
}

// Segment Tree Begin
struct lj{int Lc,Rc,L,R,flag,l,r,sum;}t[N];
void Ch(int w,int c)
{
	t[w].Lc+=c,t[w].Rc+=c;t[w].flag+=c;
}
void push(int w)
{
	if (t[w].flag!=0)
	{
		int l=w<<1;
		if (t[l].l) Ch(l,t[w].flag);
		l|=1;
		if (t[l].l) Ch(l,t[w].flag);
		t[w].flag=0;
	}
}
void update(int w)
{
	int L=w<<1,R=w<<1|1;
	if (t[L].Rc==t[R].Lc && t[R].sum==t[R].r-t[R].l+1) t[w].R=t[L].R+t[R].sum;
		else t[w].R=t[R].R;
	if (t[L].Rc==t[R].Lc && t[L].sum==t[L].r-t[L].l+1) t[w].L=t[L].sum+t[R].L;
		else t[w].L=t[L].L;
	t[w].sum=max(t[w].L,t[w].R);
	if (t[L].Rc==t[R].Lc) t[w].sum=max(t[w].sum,t[L].R+t[R].L);
	t[w].Lc=t[L].Lc;
	t[w].Rc=t[R].Rc;
}
void build(int w,int l,int r)
{
	t[w].l=l;t[w].r=r;
	if (l==r)
	{
		t[w].Lc=t[w].Rc=val[dy[l]];
		t[w].sum=t[w].L=t[w].R=1;
		return;
	}
	int mid=l+r>>1;
	build(w<<1,l,mid);build(w<<1|1,mid+1,r);
	update(w);
}
int ask_dig(int w,int l)
{
	push(w);
	if (t[w].l==t[w].r) return t[w].Lc;
	int mid=t[w].l+t[w].r>>1;
	if (l<=mid) return ask_dig(w<<1,l);
	else return ask_dig(w<<1|1,l);
}
int ask_Len(int w,int l,int r)
{
	push(w);
	if (t[w].l==l && t[w].r==r) return t[w].R;
	int mid=t[w].l+t[w].r>>1;
	if (r<=mid) return ask_Len(w<<1,l,r);
	else if (l>mid) return ask_Len(w<<1|1,l,r);
	else
	{
		int c=ask_Len(w<<1|1,mid+1,r);
		if (c<r-mid||t[w<<1].Rc!=t[w<<1|1].Lc) return c;
		else return c+ask_Len(w<<1,l,mid);
	}
}
void add(int w,int l,int r,int c)
{
	push(w);
	if (t[w].l==l && t[w].r==r)
	{
		Ch(w,c);
		return;
	}
	int mid=t[w].l+t[w].r>>1;
	if (r<=mid) add(w<<1,l,r,c);
	else if (l>mid) add(w<<1|1,l,r,c);
	else add(w<<1,l,mid,c),add(w<<1|1,mid+1,r,c);
	update(w);
}
//Segment Tree End
void Add(int x)
{
	int xx=x;
	while (x)
	{
		if (ask_dig(1,dfn[x])!=1)
		{
			add(1,dfn[x],dfn[x],1);
			break;
		}
		int c=ask_Len(1,dfn[An[x]],dfn[x]);
		add(1,max(dfn[x]-c+1,1),dfn[x],1);
		if (max(dfn[x]-c+1,1)!=1 && c!=dfn[x]-dfn[An[x]]+1) add(1,dfn[f[ dy[dfn[x]-c+1] ][0]] , dfn[f[ dy[dfn[x]-c+1] ][0]] , 1);
		if (c!=dfn[x]-dfn[An[x]]+1) break;
		x=f[An[x]][0];
	}
}
void Del(int x)
{
	int xx=x;
	while (x)
	{
		if (ask_dig(1,dfn[x])!=2)
		{
			add(1,dfn[x],dfn[x],-1);
			break;
		}
		int c=ask_Len(1,dfn[An[x]],dfn[x]);
		add(1,max(dfn[x]-c+1,1),dfn[x],-1);
		if (max(dfn[x]-c+1,1)!=1 && c!=dfn[x]-dfn[An[x]]+1) add(1,dfn[f[ dy[dfn[x]-c+1] ][0]] , dfn[f[ dy[dfn[x]-c+1] ][0]] , -1);
		if (c!=dfn[x]-dfn[An[x]]+1) break;
		x=f[An[x]][0];
	}
}

int main()
{
	read(n);int x,y,z;nn=n;
	rep(i,1,n)
	{
		read(x);read(y);read(z);
		add(i,x);add(i,y);add(i,z);
	}
	rep(i,1,n*2+1) read(col[i+n]);
	n=n*3+1;
	dfs(1,0);Dfs(1,0,1);
	n=nn;
	build(1,1,n);int m;
	read(m);
	rep(i,1,m)
	{
		read(x);
		if (!col[x])  // 0->1 find 1
		{
			col[x]^=1;
			Add(f[x][0]);
		}
		else // 1->0 find 2
		{
			col[x]^=1;
			Del(f[x][0]);
		}
		printf("%d\n",ask_dig(1,1)>1);
	}
}