真是手速场吧
D - Take ABC 2
很自然的想到倒叙匹配abc。
void solve(){cin>>s;for(int i=0;i<s.size();i++){if(s[i]=='A')A.push_back(i);else if(s[i]=='B')B.push_back(i);else if(s[i]=='C')C.push_back(i);}int ans=0;while(C.size()){int p=C.back();C.pop_back();while(!B.empty()&&B.back()>p)B.pop_back();if(B.empty())break;int u=B.back();B.pop_back();while(!A.empty()&&A.back()>u)A.pop_back();if(A.empty())break;int v=A.back();A.pop_back();ans++;}cout<<ans;
}
E - Divide Graph
并查集。刚开始的时候陷入了一个思维误区，认为前两次不相连的边确定两个根。但是实际上，这个可以这样考虑，最开始一条边都没有，有n个连通块，问加几条边可以变成2个连通块。
int n,m;
vector<pii>g[N];
struct edge{int u,v,w;
}e[N];
int fa[N],pw[N];
int find(int x){if(x==fa[x])return x;return fa[x]=find(fa[x]);
}
bool cmp(edge x,edge y){return x.w>y.w;
}
bool vis[N];
void solve(){cin>>n>>m;pw[0]=1;up(i,1,m)pw[i]=pw[i-1]*2%mod;//cout<<pw[11]<<endl;int u,v;up(i,1,n)fa[i]=i;up(i,1,m){cin>>u>>v;e[i]={u,v,i};g[u].push_back({v,i});g[v].push_back({u,i});}sort(e+1,e+1+m,cmp);int cnt=n,rt1=0,rt2=0;int ans=0;for(int i=1;i<=m;i++){if(find(e[i].u)!=find(e[i].v)){if(cnt>2){fa[find(e[i].u)]=find(e[i].v);cnt--;}else{ans=(ans+pw[e[i].w])%mod;}}}cout<<ans;
}
F - Centipede Graph
树状dp。比较简单，转移情况就两种，一种是目前点的儿子是一条蜈蚣型的末端，另一种情况是则是直接转移该子树的最大值。
int n,m;
vector<int>g[N];int f[N][2],sn[N],fa[N];
void dfs(int u,int from){int maxl1=0,maxl2=0;if(sn[u]>=2)f[u][1]=1,f[u][0]=1;if(sn[u]>=1&&from!=0)f[u][0]=1;for(auto v:g[u]){if(v==from)continue;dfs(v,u);if(f[v][1]>=maxl1){maxl2=maxl1;maxl1=f[v][1];}else{if(f[v][1]>maxl2)maxl2=f[v][1];}f[u][0]=max(f[u][0],f[v][0]);}if(u==1){if(sn[u]>=4)f[u][0]=max(f[u][0],maxl1+maxl2+1);if(sn[u]==3)f[u][0]=max(f[u][0],maxl1+1);}else {if(sn[u]>=3)f[u][0]=max(f[u][0],maxl1+maxl2+1);if(sn[u]==2)f[u][0]=max(f[u][0],maxl1+1);}if(sn[u]>=3)f[u][1]=maxl1+1;
}
void dfs1(int u,int from){for(auto v:g[u]){if(v==from)continue;sn[u]++;dfs1(v,u);}
}
void solve(){cin>>n;int u,v;up(i,1,n-1){cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}dfs1(1,0);dfs(1,0);cout<<f[1][0]<<endl;
}