F - Parenthesis Checking一直想做這種區間判括號序列合法性的題，但是一直不會，現在總算遇到了。首先，合法的括號序列的特征就是：序列

F - Parenthesis Checking

一直想做這種區間判括號序列合法性的題，但是一直不會，現在總算遇到了。

首先，合法的括號序列的特征就是：序列從前往后遍歷，右括號的數量總不大于左括號的數量，且最后左右括號的數量相同。

那么很明顯的處理方法是，將左括號視為 ，右括號視為 ，然后在遍歷序列的過程中，觀察前綴和是否為負，且區間和是否為 。

那么如何快速的處理多個詢問呢？

考慮到區間和，前綴和，區間前綴最小值，都具有區間合并的性質，那么我們用線段樹來維護信息。

那么我們判斷合法性，就是，區間最小值不小于 ，區間和為0。

考慮如何維護區間前綴最小值和區間和。

區間和就是相加。區間前綴和最小值呢？考慮兩個區間合并為一個區間 ，前一個區間的最小值保持不變，后一個區間的最小值即為前一個區間的區間和加后一個區間的最小值。

考慮每次修改為修改到根節點，每次 涉及的區間都會被更新，可在合適的復雜度內完成修改。

const int maxn=2e5+100;n#define ls ti<<1n#define rs ti<<1|1n#define midt(l+r>>1)nint n,m,a[maxn];nstring s;nstruct tree{n int l,r,sum,f;tn}t[maxn<<2];nvoid pushup(int i){ntt[i].sum=t[ls].sum+t[rs].sum;ntt[i].f=min(t[ls].f,t[ls].sum+t[rs].f);n}nvoid build(int i,int l,int r){ntt[i].l=l;tt[i].r=r;ntif(l==r){nttt[i].sum=t[i].f=a[l];nttreturn;nt}ntbuild(ls,l,mid);tn build(rs,mid+1,r);ntpushup(i);n}nvoid update(int i,int x){ntif(x>t[i].r||x<t[i].l)treturn;ntif(t[i].l==t[i].r){nttt[i].sum=t[i].f=a[x];nttreturn;nt}ntupdate(ls,x);n update(rs,x);ntpushup(i);n}ntree query(int i,int l,int r){ntif(l<=t[i].l&&t[i].r<=r)treturn t[i];ntint M=(t[i].l+t[i].r)>>1;ntif(l>M)tttreturn query(rs,l,r);ntelse if(r<=M)treturn query(ls,l,r);ntelse{ntttree ans,L,R;nttL=query(ls,l,M);tR=query(rs,M+1,r);nttans.sum=L.sum+R.sum;nttans.f=min(L.f,L.sum+R.f);nttreturn ans;nt}n}nvoid solve(){ntcin>>n>>m;ntcin>>s;ntfor(int i=0;i<n;i++) a[i+1]=(s[i]=='(')?1:-1;ntbuild(1,1,n);ntwhile(m--){nttint op,l,r;n cin>>op>>l>>r;nttif(op==1){ntttif(a[l]==a[r])tcontinue;ntttswap(a[l],a[r]);ntttupdate(1,l);tupdate(1,r);ntt}nttelse{nttttree tmp=query(1,l,r);ntttif(!tmp.sum&&!tmp.f)tcout<<"Yesn";ntttelsetcout<<"Non";ntt}nt}n}n

G - Vertex Deletion

給定一棵樹，問有多少個節點滿足：刪去這個節點后的圖的匹配數等于原樹的匹配數。

首先：匹配數 = 節點數 - 最大獨立集。

那么我們可以預處理出原樹的匹配數。設 表示 子樹中， 不選 / 選的最大獨立集大小。

然后刪去一個點后，新圖的最大獨立集大小是其他聯通塊的最大獨立集大小之和，而 兒子的子樹內最大獨立集以求出，那么我們的目標就是要求出 子樹外的最大獨立集大小。

設 表示不考慮 子樹， 的父親不選 / 選的最大獨立集大小。

轉移方程如下：

const int maxn=2e5+100;nint n,m,k;nint g[maxn][2], f[maxn][2];nvector<int>e[maxn];nvoid dfs(int u, int fa){ntf[u][1] = 1;ntfor (auto v : e[u]){nttif (v == fa) continue;nttdfs(v, u);nttf[u][0] += max(f[v][0], f[v][1]), f[u][1] += f[v][0];nt}n}n nvoid dfs1(int u, int fa){ntint s0 = 0, s1 = 0;ntfor (auto v : e[u]){nttif (v == fa) continue;ntts0 += max(f[v][0], f[v][1]), s1 += f[v][0];nt}ntfor (auto v:e[u]){nttif (v == fa) continue;nttg[v][0] = max(g[u][0], g[u][1]) + (s0 - max(f[v][0], f[v][1]));nttg[v][1] = g[u][0] + s1 - f[v][0] + 1;nttdfs1(v, u);nt}n}n nvoid solve(){ntcin>>n;ntfor (int i = 1; i < n; i+=1){nttint u,v;cin>>u>>v;ntte[u].pb(v);ntte[v].pb(u);nt}ntdfs(1, 0);ntint ans = n - max(f[1][0], f[1][1]), cnt = 0;ntdfs1(1, 0);ntfor (int i = 1; i <= n; i+=1){nttint bs = n - 1;nttint now = f[i][0] + max(g[i][0], g[i][1]);nttif (bs - now == ans) ++cnt;nt}ntcout<<cnt;n}n