【BZOJ 3924】[ZJOI2015] 幻想乡战略游戏

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3924
神犇题解:http://www.cnblogs.com/clrs97/p/4779754.html
官方题解:http://wjmzbmr.com/archives/zjoi-2015-day-1题解/

解题报告

考虑从根开始向下走
如果一个儿子的子树的权值和大于总和的一半
那么所求的点一定在这个儿子的子树中
由此可见,实际上我们所求的是这样的点:

深度最大的,子树权值和大于总权值和一半的点

这样的话,暴力找复杂度不稳定
考虑树链剖分的话,可以在\({\log ^2}(n)\)的时间复杂度内找到答案
最后考虑输出解的话,似乎直接用树链剖分不行的样子
于是似乎还得用一个点分治? (・∀・(・∀・(・∀・*)

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100000+9;
const int M = N << 1;
const int L = 18;
const int INF = 1e9;

int n,m,head[N],nxt[M],to[M],cost[M];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline void Add_Edge(int u, int v, int c) {
	static int T = 0;
	to[++T] = v; nxt[T] = head[u]; head[u] = T; cost[T] = c;
	to[++T] = u; nxt[T] = head[v]; head[v] = T; cost[T] = c;
}

class Heavy_Light_Decomposition{
	int dep[N],dis[N],fa[N],top[N],sz[N];
	int go[N],pos[N],len[N],sum,cnt;
	vector<int> que[N];
	class Fenwick_Tree{
		#define lowbit(x) ((x)&-(x))
		int arr[N];
		public:
			inline void modify(int l, int r, int delta) {
				modify(l-1, -delta);
				modify(r, delta);
			}
			inline int query(int p) {
				LL ret = 0;
				for (int i=p;i<=n;i+=lowbit(i))
					ret += arr[i];
				return ret;
			}
		private:
			inline void modify(int p, int delta) {
				for (int i=p;i;i-=lowbit(i))
					arr[i] += delta;
			}
	}BIT;
	public:
		inline void init() {
			DFS1(1, 1);
			DFS2(1, 1, 1);
		}
		inline int DIS(int u, int v) {
			int lca = LCA(u, v);
			return dis[u] + dis[v] - (dis[lca] << 1);	
		}
		inline void modify(int w, int v) {
			sum += v;
			for (;w;w=fa[top[w]]) 
				BIT.modify(pos[top[w]], pos[w], v);
		}
		inline int query() {
			int w = 1, tag = 1;
			while (tag) {
				int l = 1, r = len[w]-1, mid, ret = 0;
				while (l <= r) {
					mid = l + r >> 1;
					if (BIT.query(pos[que[w][mid]])*2 <= sum) r = mid - 1;
					else l = mid + 1, ret = mid;
				} 
				w = que[w][ret]; tag = 0;
				for (int i=head[w];i;i=nxt[i]) {
					if (dep[to[i]] > dep[w] && BIT.query(pos[to[i]])*2 > sum) {
						tag = 1; w = to[i]; break;
					}
				}
			}
 			return w;
		}
	private:
		void DFS1(int w, int f) {
			sz[w] = 1; dep[w] = dep[f] + 1;
			for (int i=head[w];i;i=nxt[i]) {
				if (to[i] != f) {
					dis[to[i]] = dis[w] + cost[i];
					fa[to[i]] = w;
					DFS1(to[i], w);
					sz[w] += sz[to[i]];
					if (sz[to[i]] > sz[go[w]])
						go[w] = to[i];
				}
			}
		}
		void DFS2(int w, int f, int t) {
			que[t].push_back(w);
			top[w] = t;	pos[w] = ++cnt;
			if (go[w]) DFS2(go[w], w, t);
			for (int i=head[w];i;i=nxt[i]) {
				if (to[i] != f && to[i] != go[w]) {
					DFS2(to[i], w, to[i]);
				}
			}
			len[w] = que[w].size();
			que[w].push_back(w);
		}
		inline int LCA(int u, int v) {
			while (top[u] != top[v]) 
				if (dep[top[u]] > dep[top[v]]) u = fa[top[u]];
				else v = fa[top[v]];
			return dep[u] > dep[v]? v: u;
		}
}HLD;

class Vertex_Based_Divide_and_Conquer{
	int sum[N],vis[N],len[N],fa[N][L],rod[N][L];
	int root,size,cur,val_sum[N],val_sum_del[N];
	LL part_ans[N],part_ans_del[N];
	public:
		inline void init() {
			int rt = Get_Root(1, n);
			len[rt] = 1;
			build(rt, n);
		}
		inline void modify(int w, int v) {
			val_sum[w] += v;
			for (int i=1,p=w,d,u;i<len[w];i++) {
				u = p; p = fa[w][i]; d = rod[w][i];
				val_sum[p] += v;
				val_sum_del[u] += v;
				part_ans[p] += (LL)v * d;
				part_ans_del[u] += (LL)v * d;
			}
		}
		inline LL query(int w) {
			LL ret = part_ans[w];
			for (int i=1,p=w,u,d;i<len[w];i++) {
				u = p; p = fa[w][i]; d = rod[w][i];
				ret += part_ans[p] + (LL)val_sum[p] * d;
				ret -= part_ans_del[u] + (LL)val_sum_del[u] * d;
			}
			return ret;
		} 
	private:
		inline int Get_Root(int w, int sz) {
			size = sz; cur = INF;
			Get_root(w, w);
			return root;
		}
		void Get_root(int w, int f) {
			int mx = 1; sum[w] = 1;
			for (int i=head[w];i;i=nxt[i]) {
				if (to[i] != f && !vis[to[i]]) {
					Get_root(to[i], w);
					sum[w] += sum[to[i]];
					mx = max(mx, sum[to[i]]);
				}
			}
			mx = max(mx, size - sum[w]);
			if (mx < cur) cur = mx, root = w;
		}
		void build(int w, int sz) {
			vis[w] = 1; fa[w][0] = w;
			for (int i=1;i<len[w];i++) 
				rod[w][i] = HLD.DIS(w, fa[w][i]);
			for (int i=head[w],tmp,rt;i;i=nxt[i]) {
				if (!vis[to[i]]) {
					tmp = sum[to[i]]<sum[w]? sum[to[i]]: sz-sum[w];
					rt = Get_Root(to[i], tmp);
					len[rt] = len[w] + 1;
					memcpy(fa[rt]+1, fa[w], sizeof(int)*len[w]);
					build(rt, tmp);
				}
			}
		}
		
}VDC;

int main() {
	n = read(); m = read();
	for (int i=1,u,v;i<n;i++) {
		u = read(); v = read();
		Add_Edge(u, v, read());
	}
	HLD.init();
	VDC.init();
	for (int i=1,p,v;i<=m;i++) {
		p = read(); v = read();
		HLD.modify(p, v);
		VDC.modify(p, v);
		p = HLD.query();
		printf("%lld\n",VDC.query(p));
	}
	return 0;
}

【HDU 5571】tree

相关链接

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=5571
数据生成器:http://paste.ubuntu.com/23672970/
中文题面:http://bestcoder.hdu.edu.cn/contests/contest_chineseproblem.php?cid=651&pid=1004
官方题解:http://oi.cyo.ng/?attachment_id=2084

解题报告

看到位运算,首先想到的就是一位一位独立来搞
酱紫的话,这题就非常简单了
直接上点分树,什么数据结构都不用套,记录零一就可以了

值得注意的是,拆二进制最好拆在最外层
因为拆在里面的话,数组会多一维,寻址的时间消耗大大增加
否则会T到死,不要问我是怎么知道的

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 30000+9;
const int M = N << 1;
const int L = 16;
const int INF = 1e9;

int n,m,T,head[N],to[M],nxt[M],cost[M],ori[N];
int val[N],dep[N],dis[N],fa[N][L],P[N],V[N];
LL ans[N];

inline void Add_Edge(int u, int v, int w) {
	to[++T] = v; nxt[T] = head[u]; head[u] = T; cost[T] = w;
	to[++T] = u; nxt[T] = head[v]; head[v] = T; cost[T] = w;
}

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

void DFS(int w, int f) {
	dep[w] = dep[f] + 1;
	fa[w][0] = f;
	for (int i=head[w];i;i=nxt[i]) {
		if (to[i] != f)  {
			dis[to[i]] = dis[w] + cost[i];
			DFS(to[i], w);
		}
	}
}

inline int LCA(int u, int v) {
	if (dep[u] < dep[v]) swap(u, v);
	for (int i=L-1;~i;i--) {
		if (dep[fa[u][i]] >= dep[v]) {
			u = fa[u][i];
		}
	}
	if (u == v) return u;
	for (int i=L-1;~i;i--) {
		if (fa[u][i] != fa[v][i]) {
			u = fa[u][i];
			v = fa[v][i];
		}
	}
	return fa[u][0];
}

inline int DIS(int u, int v) {
	int lca = LCA(u, v);
	return dis[u] + dis[v] - dis[lca] * 2;
}

class Node_Based_Divide_and_Conquer{
	int area_sz,cur_ans,root,rod[N][L],sum[N];
	int anc[N][L],len[N],tos[2][N],tot[2][N];
	bool vis[N]; LL f[2][N],sub[2][N];
	
	public:
		inline void init() {
			memset(vis,0,sizeof(vis));
			cur_ans = INF; area_sz = n;
			Get_Root(1, 1); len[root] = 1;
			Build(root, n);
		}
		
		inline void prework() {
			memset(f, 0 ,sizeof(f));
			memset(sub, 0, sizeof(sub));
			memset(tot, 0, sizeof(tot));
			memset(tos, 0, sizeof(tos));
		}
		
		inline void modify(int w, int t, int p) {
			for (int i=0,pre,cur;i<len[w];i++) {
				cur = anc[w][i];
				f[t][cur] += rod[w][i] * p;
				tot[t][cur] += p;
				if (i) {
					pre = anc[w][i-1];
					sub[t][pre] += rod[w][i] * p;
					tos[t][pre] += p;
				}
			}
		}
		
		inline LL query(int w, int t, int k) {
			LL ret = 0,s,d; t ^= 1;
			ret += f[t][w] << k;
			for (int i=1,cur,pre;i<len[w];i++) {
				cur = anc[w][i]; pre = anc[w][i-1];
				d = f[t][cur] - sub[t][pre];
				s = tot[t][cur] - tos[t][pre];
				ret += d + s * rod[w][i] << k;
			}
			return ret;
		} 
	private:
		void Get_Root(int w, int F) {
			sum[w] = 1; int mx = 0;
			for (int i=head[w];i;i=nxt[i]) {
				if (!vis[to[i]] && to[i] != F) {
					Get_Root(to[i], w);
					mx = max(sum[to[i]], mx);
					sum[w] += sum[to[i]];
				}
			}
			mx = max(mx, area_sz - sum[w]);
			if (mx < cur_ans) {
				cur_ans = mx;
				root = w;
			}
		}
		
		void Build(int w, int sz) {
			vis[w] = 1;
			anc[w][0] = w;
			for (int i=head[w];i;i=nxt[i]) {
				if (!vis[to[i]]) {
					area_sz = sum[to[i]]<sum[w]? sum[to[i]]: sz - sum[w];
					cur_ans = INF; Get_Root(to[i], w);
					len[root] = len[w] + 1; 
					memcpy(anc[root]+1, anc[w], sizeof(int)*len[w]);
					Build(root, area_sz);
				}
			}
			for (int i=0;i<len[w];i++)
				rod[w][i] = DIS(w, anc[w][i]);
		}
}NDC;

int main() {
	for (LL vout=0;~scanf("%d",&n);vout=T=0) {
		memset(head,0,sizeof(head));
		memset(ans,0,sizeof(ans));
		for (int i=1;i<=n;i++) 
			ori[i] = read();
		for (int i=1,u,v,w;i<n;i++) {
			u = read(); v = read(); w = read();
			Add_Edge(u, v, w);
		}	
		DFS(1, 1);
		for (int j=1;j<L;j++) { 
			for (int i=1;i<=n;i++) {
				fa[i][j] = fa[fa[i][j-1]][j-1];
			}
		}
		NDC.init(); 
		m = read();
		for (int i=1;i<=m;i++) {
			P[i] = read();
			V[i] = read();
		}
		for (int j=0;j<L;j++,vout=0) {
			memcpy(val,ori,sizeof(ori));
			NDC.prework();
			for (int i=1;i<=n;i++) {
				val[i] >>= j; val[i] &= 1;
				NDC.modify(i, val[i], 1);
				vout += NDC.query(i, val[i], j);
			}
			for (int i=1,p,v;i<=m;i++) {
				p = P[i]; v = (V[i] >> j) & 1;
				vout -= NDC.query(p, val[p], j);
				NDC.modify(p, val[p], -1);
				NDC.modify(p, v, 1);
				vout += NDC.query(p, val[p] = v, j);
				ans[i] += vout;
			}
		}
		for (int i=1;i<=m;i++)
			printf("%I64d\n",ans[i]);
	} 
	return 0;
}

【Codeforces 100633D】LWDB

相关链接

题目传送门:http://codeforces.com/problemset/gymProblem/100633/D
中文题面:http://paste.ubuntu.com/23661606/

解题报告

直接考虑将其用点分树搞
对于每一个合法的染色,我们尝试在第一个将染色点a被染色点b分开的分治点c处进行更新
因为是第一个分开的分治点,所以a、b一定在c的不同子树中
不妨设a的染色范围为d,那么对于任意点b来讲,距离c的距离 <= d-dis(a,c)就好

于是修改操作就暴力爬树高,维护一个单调栈
查询操作也是暴力爬树高,在每一个单调栈那里二分出最后生效的染色点即可

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100000+9;
const int M = N << 1;
const int L = 20;
const int INF = 1e9;

int head[N],to[M],nxt[M],cost[M],dis[N],dep[N];
int n,m,fa[N][L];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline void Add_Edge(int u, int v, int w) {
	static int T = 0;
	to[++T] = v; nxt[T] = head[u]; head[u] = T; cost[T] = w;
	to[++T] = u; nxt[T] = head[v]; head[v] = T; cost[T] = w;
}

void DFS(int w, int f) {
	fa[w][0] = f;
	dep[w] = dep[f] + 1;
	for (int i=head[w];i;i=nxt[i]) {
		if (to[i] != f) {
			dis[to[i]] = dis[w] + cost[i];
			DFS(to[i], w);
		}
	}
}

inline int DIS(int x, int y) {
	int ret = dis[x] + dis[y];
	if (dep[x] < dep[y]) swap(x, y);
	for (int i=L-1;~i;i--) 
		if (dep[fa[x][i]] >= dep[y]) 
			x = fa[x][i];
	if (x == y) return ret - dis[x] * 2;
	for (int i=L-1;~i;i--) {
		if (fa[x][i] != fa[y][i]) {
			x = fa[x][i];
			y = fa[y][i];
		}
	}
	return ret - dis[fa[x][0]] * 2;
}

class Node_Based_Divide_and_Conquer{
	int cur_ans,root,area_size,rod[N][L];
	int sum[N],vis[N],anc[N][L],len[N];
	struct Data{
		int x,y,z;
		inline bool operator < (const Data &B) const {return x < B.x;}
		inline bool operator <= (const Data &B) const {return x <= B.x;}
	}tmp;
	vector<Data> stk[N];
	vector<Data>::reverse_iterator itr;
	public:
		inline void init() {
			area_size = n; cur_ans = INF;
			Get_Root(1, 1); len[root] = 1;
			Build(root, n);
		}
		inline void modify(int w, int d, int c, int id) {
			tmp.y = c; tmp.z = id;
			for (int i=0,p;i<len[w];i++) {
				p = anc[w][i]; tmp.x = d - rod[w][i];
				if (tmp.x >= 0) {
					while (!stk[p].empty() && stk[p].back() <= tmp) stk[p].pop_back();
					stk[p].push_back(tmp);
				}
			}
		}
		inline int query(int w) {
			Data ret={0,0,0};
			for (int i=0,p;i<len[w];i++) {
				p = anc[w][i]; tmp.x = rod[w][i];
				itr = lower_bound(stk[p].rbegin(), stk[p].rend(), tmp);
				if (itr != stk[p].rend() && ret.z < itr->z) 
					ret = *itr;
			}
			return ret.y;
		}
	private:
		void Get_Root(int w, int f) {
			int mx = 0; sum[w] = 1;
			for  (int i=head[w];i;i=nxt[i]) {
				if (!vis[to[i]] && to[i] != f) {
					Get_Root(to[i], w);
					sum[w] += sum[to[i]];
					mx = max(mx, sum[to[i]]);
				} 
			} 
			mx = max(mx, area_size - sum[w]);
			if (mx < cur_ans) {
				cur_ans = mx;
				root = w;
			}
		} 
		void Build(int w, int sz) {
			vis[w] = 1; anc[w][0] = w;
			for (int i=head[w];i;i=nxt[i]) {
				if (!vis[to[i]]) {
					area_size = sum[to[i]] < sum[w]? sum[to[i]]: sz - sum[w];
					cur_ans = INF; Get_Root(to[i], w);
					len[root] = len[w] + 1;
					memcpy(anc[root]+1, anc[w], sizeof(anc[w])-4);
					Build(root, area_size);
				}
			}
			for (int i=1;i<len[w];i++)
				rod[w][i] = DIS(w, anc[w][i]);
		}
}NDC;

int main() {
	n = read();
	for (int i=1,u,v;i<n;i++) {
		u = read(); v = read();
		Add_Edge(u, v, read());
	}
	DFS(1, 1); 
	for (int j=1;j<L;j++) 
		for (int i=1;i<=n;i++) 
			fa[i][j] = fa[fa[i][j-1]][j-1];
	NDC.init();
	m = read();
	for (int i=1,v,d,c;i<=m;i++) {
		if (read() == 1) {
			v = read(); d = read();
			NDC.modify(v, d, read(), i);
		} else printf("%d\n",NDC.query(read()));
	}
	return 0;
}

【BZOJ 1095】[ZJOI2007] Hide 捉迷藏

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1095
数据生成器:http://paste.ubuntu.com/23659435/
神犇题解:http://blog.csdn.net/PoPoQQQ/article/details/44461423

解题报告

先建出点分树,再考虑维护三种堆
一种堆用来维护到点i的子树中所有点到点i的父亲的距离
然后第二种堆维护每一个儿子的第一种堆的最大值
第三种堆,维护所有第二种堆的最大值

酱紫话,查询之际输出第三个堆的堆顶
修改的话,就暴力在点分树上向上爬,边爬边修改

话说这题真™难写啊!
从上午11:00写到晚上12:00
真是日了哮天犬了!

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 100000+9;
const int M = N << 1;
const int INF = 1e9;
 
int head[N],to[M],nxt[M],n,m;
char pat[10],sta[N];
 
inline int read() {
    char c=getchar(); int f=1,ret=0;
    while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
    return ret * f;
}
 
inline void Add_Edge(int u, int v) {
    static int T = 0;
    to[++T] = v; nxt[T] = head[u]; head[u] = T;
    to[++T] = u; nxt[T] = head[v]; head[v] = T;
}
 
namespace Dynamic_Node_Decomposition{
    #define DND Dynamic_Node_Decomposition
    int cur,root,node_sz,cnt,in[N];
    int fa[N][18],sum[N],dep[N],len[N],vis[N];
    multiset<int> vout,s1[N],s2[N];
    multiset<int>::iterator itr;
     
    namespace Sparse_Table{
        #define ST Sparse_Table
        int _fa[N][18];
         
        inline void init() {
            for (int i=1;i<=17;i++) { 
                for (int j=1;j<=n;j++) { 
                    _fa[j][i] = _fa[_fa[j][i-1]][i-1];
                }
            }
        }
         
        inline int query(int u, int v) {
            int ret = dep[u] + dep[v];
            if (dep[u] < dep[v]) swap(u, v);
            for (int i=17;~i;i--) {
                if (dep[_fa[u][i]] >= dep[v]) {
                    u = _fa[u][i];
                }
            }
            if (u == v) return ret - dep[u] * 2;
            for (int i=17;~i;i--) {
                if (_fa[u][i] != _fa[v][i]) {
                    u = _fa[u][i];
                    v = _fa[v][i];
                }
            }
            return ret - dep[_fa[u][0]] * 2;
        }
    };
     
    void Get_root(int w, int f) {
        sum[w] = 1; int mx = 0;
        for (int i=head[w];i;i=nxt[i]) {
            if (to[i] != f && !vis[to[i]]) {
                Get_root(to[i], w);
                sum[w] += sum[to[i]];
                mx = max(mx, sum[to[i]]);
            }
        }
        mx = max(mx, node_sz - sum[w]);
        if (mx < cur) cur = mx, root = w;
    } inline int Get_Root(int w, int SZ) {
        cur = INF; node_sz = SZ;
        Get_root(w,-1);
        return root;
    }
     
    #define Delete(x, y) itr = x.lower_bound(y), x.erase(itr)
    #define Max(x) (x.size()? itr = x.end(), *--itr : -1)
    inline int Ans(multiset<int> &TMP) {
        if (TMP.size() < 2) return -1;
        else {
            int ret = *--(itr=TMP.end());
            ret += *--itr; 
            if (*itr <= -1) return -1;
            else return ret;
        } 
    }
     
    inline void modify(int w, int ty) {
        if (ty) cnt++; else cnt--;
        for (int i=0;i<len[w];i++) 
            if (sta[fa[w][i]])
                Delete(vout, Max(s2[fa[w][i]]));
        for (int i=len[w]-2,t1,t2,dis,tmp;~i;i--) {
            t1 = fa[w][i]; t2 = fa[w][i+1];
            dis = ST::query(w, t2);
            tmp = Max(s1[t1]);
            if (tmp = (tmp <= dis)) {
            	Delete(vout, Ans(s2[t2]));
        	    Delete(s2[t2], Max(s1[t1]));
			}
            if (!ty) Delete(s1[t1], dis);
            else s1[t1].insert(dis);
            if (tmp) {
				s2[t2].insert(Max(s1[t1]));
    	        vout.insert(Ans(s2[t2]));
			}
        }
        sta[w] ^= ty >= 0;
        for (int i=0;i<len[w];i++)
            if (sta[fa[w][i]]) 
                vout.insert(Max(s2[fa[w][i]]));
    }
     
    inline int query() {
        if (cnt == 0) return -1;
        else if (cnt == 1) return 0;
        else return Max(vout);
    }
     
    void DFS(int w, int f) {
        dep[w] = dep[f] + 1; ST::_fa[w][0] = f;
        for (int i=head[w];i;i=nxt[i]) 
            if (to[i] != f) DFS(to[i], w);
    } void Build(int w, int sz, int sur) {
        Get_Root(w,sz); 
        vis[w=root] = 1;  
        len[w] = len[sur] + 1;
        fa[w][0] = root;
        memcpy(fa[w]+1,fa[sur],sizeof(fa[w])-4);
        for (int i=head[w];i;i=nxt[i]) 
            if (!vis[to[i]]) 
                Build(to[i], sum[to[i]], w);
    } inline void init() {
        Build(1, n, 0);
        DFS(1, 1);
        ST::init();
        fill(sta+1, sta+1+n, 1);
        for (int i=1;i<=n;i++) { 
            s2[fa[i][1]].insert(-1);
            vout.insert(-1);
            vout.insert(-1);
        }
        for (int i=1;i<=n;i++)
            modify(i, -1);
    }
};
 
int main() {
    n = read(); 
    for (int i=1;i<n;i++)
        Add_Edge(read(), read());
    DND::init();
    m = read();
    for (int i=1,p;i<=m;i++) {
        scanf("%s",pat+1);
        if (pat[1] == 'C') {
            p = read();
            if (sta[p]) DND::modify(p, 0);
            else DND::modify(p, 1);
        } else {
            printf("%d\n",DND::query());
        }
    } 
    return 0;
}

原谅我为了好写而各种封装而造成的巨大常数 QwQ