A,B很简单，跳过了。

C题规律相当明显，可以直接对\(2^n-1\)打表，也可以不打表直接算最大因数。

D题两种操作转化一下DP即可。

E题考虑查分数组不变的性质。

F题考虑dfs时动态维护每个叶子的深度，从一个节点走向它的孩子相当于孩子对应的区间加，不包含孩子的区间减。

#include 
    
     using namespace std;typedef long long ll;const int P=1050000;const int N=500010;int u;ll st[P],tag[P],tg;void pushup(int x){  st[x]=min(st[x<<1],st[x<<1|1])+tag[x];}void Add(int s,int t,ll v){  int ss=u+s,tt=u+t;  for (s+=u-1,t+=u+1; s^t^1; pushup(ss>>=1),pushup(tt>>=1),s>>=1,t>>=1){    if (~s&1) st[s^1]+=v,tag[s^1]+=v;    if (t&1) st[t^1]+=v,tag[t^1]+=v;  }  for (s>>=1,t>>=1; s!=t; s>>=1,t>>=1) pushup(s),pushup(t);  for (; s; s>>=1) pushup(s);}ll ask(int s,int t){  ll retl=LLONG_MAX>>1,retr=retl;  int ss=u+s,tt=u+t;  for (s+=u-1,t+=u+1; s^t^1; retl+=tag[ss>>=1],retr+=tag[tt>>=1],s>>=1,t>>=1){    if (~s&1) retl=min(retl,st[s^1]);    if (t&1) retr=min(retr,st[t^1]);  }  for (s>>=1,t>>=1; s!=t; s>>=1,t>>=1) retl+=tag[s],retr+=tag[t];  retl=min(retl,retr);  for (; s; s>>=1) retl+=tag[s];  return retl;}int clk,dfn[N],en[N];vector
     
      
        > g[N];vector
       
         a[N];ll ans[N];int la[N],ra[N];void dfs(int x,ll dep){  //cerr<
        
         <<" "<
         
          <
          
           >1; for (auto j:g[x]) dfs(j.first,dep+j.second); en[x]=clk;}void dfs2(int x){ for (auto j:a[x]) ans[j]=tg+ask(la[j],ra[j]); for (auto j:g[x]){ tg+=j.second; Add(dfn[j.first],en[j.first],-j.second*2); dfs2(j.first); Add(dfn[j.first],en[j.first],j.second*2); tg-=j.second; }}int n,q;int main(){ scanf("%d%d",&n,&q); for (int i=2; i<=n; ++i){ int x,y; scanf("%d%d",&x,&y); g[x].push_back(make_pair(i,y)); } for (u=1; u
           
            >1; for (int i=u; i; --i) st[i]=min(st[i<<1],st[i<<1|1]); for (int i=1; i<=q; ++i){ int x; scanf("%d%d%d",&x,&la[i],&ra[i]); a[x].push_back(i); } //cerr<<"????"<
           
          
         
        
       
      
     
    

这个zkw写得我好恶心，早知道还是写普通线段树了。

G题非常神仙，先考虑构造一个

1------2---------3

......... |______4

来代替1这个原有的白点。

然后原图就没有染过色的点了。

考虑有度为4的点那么先手必胜。

如果有度为3且第二长的儿子比2长的点，那么先手必胜。

考虑你现在只可能有最多两个度为3的点了。

只有0或1个3度点，那么是和局。

两个的话，必定组成一根“骨头”，分奇偶讨论即可。

#include 
    
     using namespace std;vector
     
      
        > G;vector
       
         vis;void aDD(int x,int y){  if (x>=G.size()) G.resize(x+1);  if (y>=G.size()) G.resize(y+1);  G[x].push_back(y);  G[y].push_back(x);}bool dfs(int x,int len){  vis[x]=1;  if (G[x].size()>=3&&len&&len%2==0) return 1;  for (auto j:G[x])    if (!vis[j]&&dfs(j,len+1)) return 1;  return 0;}int n,t;string s;int main(){  ios_base::sync_with_stdio(false); cin.tie(NULL);  int t; cin>>t;  while (t--){    cin>>n;    G=*(new vector
        
         
           >(2)); vis.clear(); for (int i=1; i
          
           >u>>v; aDD(u,v); } int cnt=n; cin>>s; for (int i=1; i<=n; ++i) if (s[i-1]=='W'){ aDD(i,cnt+1); aDD(cnt+1,cnt+2); aDD(cnt+1,cnt+3); cnt+=3; } vis.resize(cnt+1); for (int i=1; i<=cnt; ++i) if (G[i].size()>=4) goto l1; for (int i=1; i<=cnt; ++i) if (G[i].size()>=3){ vector
           
             v; for (auto j:G[i]) v.push_back(G[j].size()); sort(v.rbegin(),v.rend()); if (v[1]>=2) goto l1; } for (int i=1; i<=cnt; ++i) if (G[i].size()>=3&&dfs(i,0)) goto l1; puts("Draw"); continue; l1:puts("White"); }}
           
          
         
        
       
      
     
    

H题虽然不那么神仙，但是代码难度爆炸，错了也不知道怎么调QAQ

首先每个符合区间限制的数肯定一一对应正则表达式的个数。

于是你只需要统计正则表达式的个数就可以了。

将正则表达式映射到AC自动机上，

DP时在AC自动机上走就行了，同时询问一下该节点剩余长度匹配的正则表达式个数。

并不需要关心后面具体填了什么，因为只要长度够，就符合正则表达式。

一堆细节，十分恶心。

#include 
    
     using namespace std;const int N=2005;const int M=805;const int NODE=M*20;const int INF=~0u>>1;int trans[NODE][10],fail[NODE],tot;int val[NODE][M];int f[N][NODE];bool way[N][NODE];string l,r;int n,m;void depth(int now,int p,bool dlim,bool ulim){    if (now>=m){        //cerr<<"ADD"<
     
<<" "<<0<