We hope you enjoyed these problems!↵
↵
[problem:2222A]↵
↵
Author: [user:Lyz09,2026-04-26]↵
↵
<spoiler summary="Hint 1">↵
Consider the case where $k=1$.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2222A]↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
#include<iostream>↵
using namespace std;↵
int t,n;↵
int main()↵
{↵
cin>>t;↵
while(t--)↵
{↵
cin>>n;↵
bool ans=false;↵
for(int i=1;i<=n;i++)↵
{↵
int x;↵
cin>>x;↵
if(x==100)↵
ans=true;↵
}↵
if(ans)↵
cout<<"Yes"<<endl;↵
else↵
cout<<"No"<<endl;↵
}↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
[problem:2222B]↵
↵
Author: [user:lizhous,2026-04-26]↵
↵
<spoiler summary="Hint 1">↵
Consider for a given $p$, which elements can be placed at $p$ with one reversal operation.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2222B]↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
#include<iostream>↵
#include<cstdio>↵
#include<algorithm>↵
#include<queue>↵
#define int long long↵
using namespace std;↵
int n,a,x,m,sum;↵
priority_queue <int> nm[2];↵
bool hv[2];↵
signed main()↵
{↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
cout.tie(0);↵
int T;↵
cin>>T;↵
while(T--)↵
{↵
sum=0;↵
hv[0]=hv[1]=0;↵
while(!nm[0].empty()) nm[0].pop();↵
while(!nm[1].empty()) nm[1].pop();↵
cin>>n>>m;↵
for(int i=1;i<=n;i++)↵
{↵
cin>>a;↵
nm[i&1].push(a);↵
sum+=a;↵
}↵
for(int i=1;i<=m;i++)↵
{↵
cin>>x;↵
if((!nm[x&1].empty()&&nm[x&1].top()>=0)||!hv[x&1])↵
{↵
sum-=nm[x&1].top();↵
nm[x&1].pop();↵
hv[x&1]=1;↵
}↵
}↵
cout<<sum<<"\n";↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2222C]↵
↵
Author: [user:ma2021tyoi0037,2026-04-26]↵
↵
<spoiler summary="Hint 1">↵
Consider how to determine whether the median of an interval equals $x$.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
What could be the median of each subsequence?↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2222C]↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
#include<iostream>↵
#include<cstring>↵
#include<algorithm>↵
#include<cmath>↵
using namespace std;↵
const int N=5e3+10;↵
int n,a[N],b[N],mid,dp[N];↵
void run(){↵
cin>>n;↵
for(int i=1;i<=n;i++)cin>>a[i];↵
memcpy(b+1,a+1,n<<2);↵
sort(b+1,b+n+1);↵
mid=b[(n+1)>>1];↵
for(int i=1;i<=n;i++){↵
if(a[i]==mid){↵
a[i]=0;↵
continue;↵
}↵
a[i]=(a[i]>mid?1:-1);↵
}↵
for(int i=1,flg=0;i<=n;i++){↵
dp[i]=0;↵
flg=!a[i];↵
if(flg and (i==1 or dp[i-1]))dp[i]=dp[i-1]+1;↵
for(int j=i-3,sm=a[i];j>=0;j-=2){↵
flg+=!a[j+1];↵
flg+=!a[j+2];↵
sm+=a[j+1]+a[j+2];↵
if(abs(sm)>=flg or (j and !dp[j]))continue;↵
dp[i]=max(dp[i],dp[j]+1);↵
}↵
// cout<<dp[i]<<" \n"[i==n];↵
}↵
cout<<dp[n]<<'\n';↵
}↵
int main(){↵
cin.tie(0);↵
cout.tie(0);↵
ios::sync_with_stdio(0);↵
int T;↵
cin>>T;↵
while(T--)run();↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2222D]↵
↵
Author: [user:Lyz09,2026-04-26]↵
↵
<spoiler summary="Hint 1">↵
Try to perform a prefix sum on $a$.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Consider what the upper bound of the answer is.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2222D]↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
#include<iostream>↵
#include<algorithm>↵
using namespace std;↵
#define N 200010↵
int t,n,a[N],p[N];↵
pair<long long,int> b[N];↵
int main()↵
{↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
cout.tie(0);↵
cin>>t;↵
while(t--)↵
{↵
cin>>n;↵
b[0].first=0;↵
for(int i=1;i<=n;i++)↵
{↵
cin>>a[i];↵
b[i].first=b[i-1].first+a[i];↵
b[i].second=i;↵
}↵
for(int i=n;i>=1;i--)↵
b[i].first=b[i-1].first;↵
sort(b+1,b+n+1);↵
for(int i=n;i>=1;i--)↵
p[b[i].second]=n-i+1;↵
for(int i=1;i<=n;i++)↵
cout<<p[i]<<" \n"[i==n];↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2222E]↵
↵
Author: [user:Lyz09,2026-04-26]↵
↵
<spoiler summary="Hint 1">↵
Try to use $0$ and $2^n-1$ in the solution.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2222E]↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
#include<iostream>↵
#include<set>↵
using namespace std;↵
int t,n;↵
set<long long> s;↵
int makeI(long long x)↵
{↵
cout<<"I "<<x<<endl;↵
int ans=0;↵
cin>>ans;↵
return ans;↵
}↵
int makeQ(long long y)↵
{↵
cout<<"Q "<<y<<endl;↵
int ans=0;↵
cin>>ans;↵
return ans;↵
}↵
int query(long long x)↵
{↵
int res=makeQ(x);↵
for(long long w:s)↵
if(w>=x)↵
res--;↵
return res;↵
}↵
long long guess(int n)↵
{↵
long long pre=0;↵
for(int i=n-1;i>=0;i--)↵
if(query(pre|(1ll<<i))>0)↵
{↵
pre|=(1ll<<i);↵
}↵
return pre;↵
}↵
int main()↵
{↵
cin>>t;↵
while(t--)↵
{↵
cin>>n;↵
s.clear();↵
cout<<0<<endl;↵
s.insert(0);↵
int res1=makeI(0);↵
if(res1==1)↵
{↵
makeI((1ll<<n)-1);↵
long long w=guess(n);↵
cout<<"A "<<1<<" "<<w<<endl;↵
continue;↵
}↵
long long c=guess(n);↵
s.insert(c);↵
if(c==(1ll<<n)-1)↵
{↵
int res2=makeI(1);↵
if(res2!=res1)↵
{↵
cout<<"A "<<3<<" "<<c<<endl;↵
}↵
else↵
{↵
cout<<"A "<<2<<" "<<c<<endl;↵
}↵
continue;↵
}↵
int res2=makeI((1ll<<n)-1);↵
if(query((1ll<<n)-1)>0)↵
{↵
cout<<"A "<<2<<" "<<c<<endl;↵
}↵
else↵
{↵
cout<<"A "<<3<<" "<<c<<endl;↵
}↵
}↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
↵
↵
[problem:2222F]↵
↵
Author: [user:hzy_____,2026-04-26]↵
Preparation: [user:Rebex,2026-04-26]↵
↵
<spoiler summary="Hint 1">↵
Under what circumstances can an edge with cost $w$ be added between vertex $u$ and vertex $v$ in a new graph?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Consider divide and conquer.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2222F]↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
#include <iostream>↵
#include <algorithm>↵
#include <cstdio>↵
#include <vector>↵
↵
using namespace std;↵
↵
const int S=300005;↵
↵
int n,m,k;↵
vector<pair<int,int> > vec[S];↵
int fa[S],hei[S],pt[S],fa2[S];↵
int top,*pot[S*3],val[S*3];↵
long long ans;↵
↵
int fnd(int x){return fa[x]==x?x:fnd(fa[x]);}↵
int fnd2(int x){return fa2[x]==x?x:fa2[x]=fnd2(fa2[x]);}↵
↵
inline void push(int &x){pot[++top]=&x,val[top]=x;}↵
inline void pop(){*pot[top]=val[top],top--;}↵
↵
inline void merge(int x,int y,int w)↵
{↵
int rx=fnd(x),ry=fnd(y);↵
if(rx==ry) return;↵
int px=pt[rx],py=pt[ry];↵
if(px!=0&&py!=0)↵
{↵
int rx=fnd2(px),ry=fnd2(py);↵
if(rx!=ry) ans+=w,fa2[rx]=fa2[ry];↵
}↵
if(hei[rx]>hei[ry]) swap(rx,ry);↵
push(hei[ry]),hei[ry]=max(hei[ry],hei[rx]+1);↵
push(pt[ry]),pt[ry]=max(pt[ry],pt[rx]);↵
push(fa[rx]),fa[rx]=ry;↵
}↵
↵
void doit(int l,int r,int w)↵
{↵
if(l==r) return;↵
int tp=top;↵
int mid=l+r>>1;↵
for(int i=r;i>=mid+1;i--)↵
for(auto t:vec[i]) merge(t.first,t.second,w);↵
doit(l,mid,w);↵
while(top>tp) pop();↵
for(int i=l;i<=mid;i++)↵
{↵
if(!vec[i].empty()&&w==i) w++;↵
for(auto t:vec[i]) merge(t.first,t.second,w);↵
}↵
doit(mid+1,r,w);↵
while(top>tp) pop();↵
}↵
↵
inline void slove()↵
{↵
cin>>n>>m>>k;↵
for(int i=0;i<=m;i++) vec[i].clear();↵
for(int i=1,x,y,w;i<=m;i++) cin>>x>>y>>w,vec[w].emplace_back(x,y);↵
vector<int> tmp;↵
for(int i=1,x;i<=k;i++) cin>>x,tmp.push_back(x);↵
sort(tmp.begin(),tmp.end());↵
tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());↵
k=tmp.size();↵
for(int i=1;i<=n;i++) pt[i]=0;↵
for(int i=0;i<k;i++) pt[tmp[i]]=i+1;↵
for(int i=1;i<=n;i++) fa[i]=i,hei[i]=1;↵
for(int i=1;i<=k;i++) fa2[i]=i;↵
ans=0;↵
doit(0,m,0);↵
for(int i=1;i<=k;i++) if(fnd2(i)!=fnd2(1)) return cout<<"-1\n",void();↵
cout<<ans<<'\n';↵
}↵
↵
int main()↵
{↵
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);↵
int T;↵
cin>>T;↵
while(T-->0) slove();↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2222G]↵
↵
Author: [user:Lyz09,2026-04-26]↵
Developer: [user:Z-301,2026-04-26]↵
↵
<spoiler summary="Hint 1">↵
What is the value of a path that passes through the centroid of a tree?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
What is the value of a path that does not pass through the centroid of a tree?↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
This is a convolution problem. Enumerate only the terms in the polynomial with non-zero coefficients and prove that the time complexity is correct.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2222G]↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
#include <algorithm>↵
#include <cstring>↵
#include <cstdio>↵
#include <vector>↵
#include <queue>↵
using namespace std;↵
typedef long long ll;↵
typedef vector<int> vi;↵
class edge{↵
public:↵
edge(int x, int y, int z, int zz){v = x, w = y, c = z, nxt = zz;}↵
int v, w, c, nxt;↵
};↵
class graph{↵
private:↵
vector<int> head;vector<edge> e;↵
public:↵
void init(int n){head.clear(), e.clear();for (int i = 0;i <= n;i ++) head.emplace_back(-1);}↵
graph(){}graph(int n){init(n);}↵
inline int addedge(int u, int v, int w = 0, int c = 0){e.emplace_back(v, w, c, head[u]), head[u] = e.size() - 1;return e.size() - 1;}↵
inline int add2edge(int u, int v, int w = 0){int tmp = addedge(u, v, w);addedge(v, u, w);return tmp;}↵
inline int addfedge(int u, int v, int w, int c = 0){int tmp = addedge(u, v, w, c);addedge(v, u, 0, -c);return tmp;}↵
inline int& h(int u){return head[u];}↵
inline edge& operator[](int i){return e[i];}↵
}G;↵
const int N = 100005;ll ans[N];vi a[N];vector<ll> b[N];↵
int t, n, al, mns, rt, sz[N], cnt[N];↵
void dfs(int u, int fa){int mx = 0;sz[u] = 1;↵
for (int i = G.h(u);i != -1;i = G[i].nxt){↵
int v = G[i].v;if (v == fa) continue;↵
dfs(v, u), sz[u] += sz[v], mx = max(mx, sz[v]);↵
}mx = max(mx, al - sz[u]);↵
if (mx < mns) rt = u, mns = mx;↵
}↵
void dfs1(int u, int fa, int mx, int rt){↵
a[rt].push_back(max(mx, sz[u]));↵
for (int i = G.h(u);i != -1;i = G[i].nxt){↵
int v = G[i].v;if (v == fa) continue;↵
dfs1(v, u, max(mx, sz[u] - sz[v]), rt);↵
}↵
}↵
void calc(vi& a, vector<ll>& s, vi& b, int o){↵
int p = upper_bound(a.begin(), a.end(), o) - a.begin();↵
for (int i = 0, j;i < b.size();i ++){↵
j = upper_bound(a.begin(), a.end(), b[i]) - a.begin();↵
if (b[i] > o) ans[o] -= j, ans[b[i]] += j;j = max(j, p);↵
if (j < a.size()) ans[o] -= a.size() - j, s[j] ++;↵
}↵
}↵
void dfs2(int u, int fa){vi vc;↵
for (int i = G.h(u);i != -1;i = G[i].nxt){↵
int v = G[i].v, w = sz[v];if (v == fa) continue;↵
ans[n - w - w] += 1ll * cnt[w] * w, cnt[w] += w, vc.push_back(w);↵
}sort(vc.begin(), vc.end()), vc.erase(unique(vc.begin(), vc.end()), vc.end());↵
for (int x : vc) for (int y : vc) if (x < y)↵
ans[n - x - y] += 1ll * cnt[x] * cnt[y];↵
for (int v : vc) ans[n - v] += (u != rt) * cnt[v], cnt[v] = 0;↵
for (int i = G.h(u);i != -1;i = G[i].nxt){↵
int v = G[i].v;if (v != fa) dfs2(v, u);}↵
}↵
void solve(int u){vi to;↵
for (int i = G.h(u);i != -1;i = G[i].nxt){↵
int v = G[i].v;to.push_back(v), dfs1(v, u, 0, v);↵
sort(a[v].begin(), a[v].end()), b[v].resize(a[v].size(), 0);↵
}↵
for (int x : to) if (sz[x] * 3 >= n) for (int y : to) if (x < y || sz[y] * 3 < n) calc(a[x], b[x], a[y], n - sz[x] - sz[y]);↵
for (int v : to){ll ls = 0;↵
for (ll& x : b[v]) ls = x += ls;↵
for (int i = 0;i < a[v].size();i ++)↵
ans[max(a[v][i], n - sz[v])] ++,↵
ans[a[v][i]] += b[v][i];a[v].clear(), b[v].clear();↵
}dfs2(rt, 0);↵
}↵
int main(){scanf("%d", &t);↵
while (t --){scanf("%d", &n), G.init(n);↵
for (int i = n - 1, u, v;i --;)↵
scanf("%d%d", &u, &v), G.add2edge(u, v);memset(ans, 0, n + 1 << 3);↵
al = n, mns = N, dfs(1, 0), dfs(rt, 0), solve(rt), ans[n] += n;↵
for (int i = 1;i <= n;i ++) printf("%lld ", ans[i]);putchar('\n');↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2222H]↵
↵
Author: [user:CutieSmileHaruka,2026-04-26]↵
↵
<spoiler summary="Hint 1">↵
You are given an array $a$. How to count the number of arrays $b$ that satisfy $f(b) = a$ and $ \forall 1 \le i \le n, b_i \le r_i $.?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
You are given an array $a$. How to count the number of arrays $b$ that satisfy $f(f(b)) = a$ and $ \forall 1 \le i \le n, b_i \le r_i $.?↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
How many arrays $a$ satisfy there exists an array $b$ such that $f(f(b)) = a$?↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
[The partition numbers](https://oeis.org/A000041).↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2222H]↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
// 全身全霊！MORE MORE JUMP!!↵
#include <algorithm>↵
#include <cstring>↵
#include <cstdio>↵
#include <vector>↵
#include <queue>↵
#define mod 998244353↵
using namespace std;↵
typedef __int128_t lll;↵
template<typename T, const int M>↵
struct BHasher{inline int operator()(T x){return x % M;}};↵
template<typename T1, typename T2, int M, typename Hsr = BHasher<T1, M>>↵
struct HashMap{↵
struct node{int nx;T1 ky;T2 vl;};↵
int h[M];vector<node> nd;Hsr hsh;↵
HashMap(){memset(h, -1, sizeof(h));}↵
void clear(){memset(h, -1, sizeof(h)), nd.clear();}↵
inline bool find(T1 k){int p = hsh(k);↵
for (int i = h[p];i != -1;i = nd[i].nx)↵
if (nd[i].ky == k) return 1;return 0;↵
}↵
inline T2& operator[](T1 k){int p = hsh(k);↵
for (int i = h[p];i != -1;i = nd[i].nx)↵
if (nd[i].ky == k) return nd[i].vl;↵
nd.push_back((node){h[p], k, T2()});↵
return nd[h[p] = nd.size() - 1].vl;↵
}↵
};↵
const int N = 55, K = 1005, M = 1296000;HashMap<lll, int, 1919839> id;↵
int t, n, m, k, c, a[N], fa[M], to[M][N], C[N][N], f[M], ans[K], rt, cnt;↵
unsigned char b[M][N], bb[N], ps[M][N], sk[N], tmp[N], sm[M], ct[M], dep[M];↵
void dfs(int p, int sm){↵
if (p > n){m ++;↵
memcpy(ps[m], sk, sizeof(sk));↵
memcpy(b[m], bb, sizeof(bb));↵
return;↵
}↵
for (int x = 0;x <= n && sm <= n;x ++, sm += p){↵
if (x) sk[++ c] = p;↵
bb[p] = x, dfs(p + 1, sm);↵
if (x) sk[c --] = 0;↵
}↵
}↵
inline lll hsh(unsigned char* A){lll st = 0;↵
for (int i = 1;i <= n;i ++)↵
st <<= 1, st |= 1, st <<= A[i];return st;↵
}↵
inline unsigned char gdep(int x){return dep[x] ? dep[x] : dep[x] = gdep(fa[x]) + 1;}↵
inline void add(int& x, int y){x += y;if (x >= mod) x -= mod;}↵
int main(){scanf("%d", &t), n = N - 5;↵
for (int i = 0;i <= n;i ++){C[i][0] = 1;↵
for (int j = 1;j <= i;j ++) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;}↵
while (t --){scanf("%d%d", &n, &k), m = cnt = 0, dfs(1, 0);↵
memset(dep, 0, m + 1 << 1), memset(f, 0, m + 1 << 2), memset(ans, 0, k + 1 << 2);↵
for (int i = 1;i <= n;i ++) scanf("%d", &a[i]);↵
for (int i = 1;i <= m;i ++){↵
lll st = hsh(b[i]);id[st] = i;↵
for (int j = n, p = -1;j >= 1;j --){↵
p += b[i][j] + 1;if (b[i][j])↵
to[i][j] = id[((st >> p) << p - 1) | (st & ((lll)1 << p) - 1)];↵
}↵
}↵
for (int i = 1;i <= m;i ++){↵
memset(tmp, 0, sizeof(tmp)), sm[i] = ct[i] = 0;↵
for (int j = 1;j <= n;j ++)↵
tmp[b[i][j]] ++, sm[i] += j * b[i][j], ct[i] += b[i][j];↵
if (sm[i] == 1) rt = i;↵
fa[i] = id[hsh(tmp)];↵
}f[1] = dep[1] = dep[rt] = 1;↵
for (int i = n, ss = 0;i >= 1;i --){↵
for (int o = 1;o <= n;o ++) ss += a[o] == i;↵
for (int j = m;j >= 1;j --)↵
if (ct[j] <= n - i + 1 && sm[j] <= ss)↵
for (int k = 1, x, now;ps[j][k];k ++)↵
if (now = f[to[j][x = ps[j][k]]])↵
f[j] = (f[j] + 1ll * now * C[ss - sm[j] + x][x]) % mod;↵
}↵
for (int i = 2;i <= m;i ++) add(ans[gdep(i) + 2], f[i]);↵
for (int i = 1;i <= n;i ++) cnt += a[i] > 0;↵
add(ans[3], mod - cnt), add(ans[2], cnt - (a[1] > 0)), add(ans[1], 1 + (a[1] > 0));↵
for (int i = 1;i <= k;i ++) printf("%d ", ans[i]);putchar('\n');↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
[problem:2222A]↵
↵
Author: [user:Lyz09,2026-04-26]↵
↵
<spoiler summary="Hint 1">↵
Consider the case where $k=1$.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2222A]↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
#include<iostream>↵
using namespace std;↵
int t,n;↵
int main()↵
{↵
cin>>t;↵
while(t--)↵
{↵
cin>>n;↵
bool ans=false;↵
for(int i=1;i<=n;i++)↵
{↵
int x;↵
cin>>x;↵
if(x==100)↵
ans=true;↵
}↵
if(ans)↵
cout<<"Yes"<<endl;↵
else↵
cout<<"No"<<endl;↵
}↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
[problem:2222B]↵
↵
Author: [user:lizhous,2026-04-26]↵
↵
<spoiler summary="Hint 1">↵
Consider for a given $p$, which elements can be placed at $p$ with one reversal operation.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2222B]↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
#include<iostream>↵
#include<cstdio>↵
#include<algorithm>↵
#include<queue>↵
#define int long long↵
using namespace std;↵
int n,a,x,m,sum;↵
priority_queue <int> nm[2];↵
bool hv[2];↵
signed main()↵
{↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
cout.tie(0);↵
int T;↵
cin>>T;↵
while(T--)↵
{↵
sum=0;↵
hv[0]=hv[1]=0;↵
while(!nm[0].empty()) nm[0].pop();↵
while(!nm[1].empty()) nm[1].pop();↵
cin>>n>>m;↵
for(int i=1;i<=n;i++)↵
{↵
cin>>a;↵
nm[i&1].push(a);↵
sum+=a;↵
}↵
for(int i=1;i<=m;i++)↵
{↵
cin>>x;↵
if((!nm[x&1].empty()&&nm[x&1].top()>=0)||!hv[x&1])↵
{↵
sum-=nm[x&1].top();↵
nm[x&1].pop();↵
hv[x&1]=1;↵
}↵
}↵
cout<<sum<<"\n";↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2222C]↵
↵
Author: [user:ma2021tyoi0037,2026-04-26]↵
↵
<spoiler summary="Hint 1">↵
Consider how to determine whether the median of an interval equals $x$.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
What could be the median of each subsequence?↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2222C]↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
#include<iostream>↵
#include<cstring>↵
#include<algorithm>↵
#include<cmath>↵
using namespace std;↵
const int N=5e3+10;↵
int n,a[N],b[N],mid,dp[N];↵
void run(){↵
cin>>n;↵
for(int i=1;i<=n;i++)cin>>a[i];↵
memcpy(b+1,a+1,n<<2);↵
sort(b+1,b+n+1);↵
mid=b[(n+1)>>1];↵
for(int i=1;i<=n;i++){↵
if(a[i]==mid){↵
a[i]=0;↵
continue;↵
}↵
a[i]=(a[i]>mid?1:-1);↵
}↵
for(int i=1,flg=0;i<=n;i++){↵
dp[i]=0;↵
flg=!a[i];↵
if(flg and (i==1 or dp[i-1]))dp[i]=dp[i-1]+1;↵
for(int j=i-3,sm=a[i];j>=0;j-=2){↵
flg+=!a[j+1];↵
flg+=!a[j+2];↵
sm+=a[j+1]+a[j+2];↵
if(abs(sm)>=flg or (j and !dp[j]))continue;↵
dp[i]=max(dp[i],dp[j]+1);↵
}↵
// cout<<dp[i]<<" \n"[i==n];↵
}↵
cout<<dp[n]<<'\n';↵
}↵
int main(){↵
cin.tie(0);↵
cout.tie(0);↵
ios::sync_with_stdio(0);↵
int T;↵
cin>>T;↵
while(T--)run();↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2222D]↵
↵
Author: [user:Lyz09,2026-04-26]↵
↵
<spoiler summary="Hint 1">↵
Try to perform a prefix sum on $a$.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Consider what the upper bound of the answer is.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2222D]↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
#include<iostream>↵
#include<algorithm>↵
using namespace std;↵
#define N 200010↵
int t,n,a[N],p[N];↵
pair<long long,int> b[N];↵
int main()↵
{↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
cout.tie(0);↵
cin>>t;↵
while(t--)↵
{↵
cin>>n;↵
b[0].first=0;↵
for(int i=1;i<=n;i++)↵
{↵
cin>>a[i];↵
b[i].first=b[i-1].first+a[i];↵
b[i].second=i;↵
}↵
for(int i=n;i>=1;i--)↵
b[i].first=b[i-1].first;↵
sort(b+1,b+n+1);↵
for(int i=n;i>=1;i--)↵
p[b[i].second]=n-i+1;↵
for(int i=1;i<=n;i++)↵
cout<<p[i]<<" \n"[i==n];↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2222E]↵
↵
Author: [user:Lyz09,2026-04-26]↵
↵
<spoiler summary="Hint 1">↵
Try to use $0$ and $2^n-1$ in the solution.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2222E]↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
#include<iostream>↵
#include<set>↵
using namespace std;↵
int t,n;↵
set<long long> s;↵
int makeI(long long x)↵
{↵
cout<<"I "<<x<<endl;↵
int ans=0;↵
cin>>ans;↵
return ans;↵
}↵
int makeQ(long long y)↵
{↵
cout<<"Q "<<y<<endl;↵
int ans=0;↵
cin>>ans;↵
return ans;↵
}↵
int query(long long x)↵
{↵
int res=makeQ(x);↵
for(long long w:s)↵
if(w>=x)↵
res--;↵
return res;↵
}↵
long long guess(int n)↵
{↵
long long pre=0;↵
for(int i=n-1;i>=0;i--)↵
if(query(pre|(1ll<<i))>0)↵
{↵
pre|=(1ll<<i);↵
}↵
return pre;↵
}↵
int main()↵
{↵
cin>>t;↵
while(t--)↵
{↵
cin>>n;↵
s.clear();↵
cout<<0<<endl;↵
s.insert(0);↵
int res1=makeI(0);↵
if(res1==1)↵
{↵
makeI((1ll<<n)-1);↵
long long w=guess(n);↵
cout<<"A "<<1<<" "<<w<<endl;↵
continue;↵
}↵
long long c=guess(n);↵
s.insert(c);↵
if(c==(1ll<<n)-1)↵
{↵
int res2=makeI(1);↵
if(res2!=res1)↵
{↵
cout<<"A "<<3<<" "<<c<<endl;↵
}↵
else↵
{↵
cout<<"A "<<2<<" "<<c<<endl;↵
}↵
continue;↵
}↵
int res2=makeI((1ll<<n)-1);↵
if(query((1ll<<n)-1)>0)↵
{↵
cout<<"A "<<2<<" "<<c<<endl;↵
}↵
else↵
{↵
cout<<"A "<<3<<" "<<c<<endl;↵
}↵
}↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
↵
↵
[problem:2222F]↵
↵
Author: [user:hzy_____,2026-04-26]↵
Preparation: [user:Rebex,2026-04-26]↵
↵
<spoiler summary="Hint 1">↵
Under what circumstances can an edge with cost $w$ be added between vertex $u$ and vertex $v$ in a new graph?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Consider divide and conquer.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2222F]↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
#include <iostream>↵
#include <algorithm>↵
#include <cstdio>↵
#include <vector>↵
↵
using namespace std;↵
↵
const int S=300005;↵
↵
int n,m,k;↵
vector<pair<int,int> > vec[S];↵
int fa[S],hei[S],pt[S],fa2[S];↵
int top,*pot[S*3],val[S*3];↵
long long ans;↵
↵
int fnd(int x){return fa[x]==x?x:fnd(fa[x]);}↵
int fnd2(int x){return fa2[x]==x?x:fa2[x]=fnd2(fa2[x]);}↵
↵
inline void push(int &x){pot[++top]=&x,val[top]=x;}↵
inline void pop(){*pot[top]=val[top],top--;}↵
↵
inline void merge(int x,int y,int w)↵
{↵
int rx=fnd(x),ry=fnd(y);↵
if(rx==ry) return;↵
int px=pt[rx],py=pt[ry];↵
if(px!=0&&py!=0)↵
{↵
int rx=fnd2(px),ry=fnd2(py);↵
if(rx!=ry) ans+=w,fa2[rx]=fa2[ry];↵
}↵
if(hei[rx]>hei[ry]) swap(rx,ry);↵
push(hei[ry]),hei[ry]=max(hei[ry],hei[rx]+1);↵
push(pt[ry]),pt[ry]=max(pt[ry],pt[rx]);↵
push(fa[rx]),fa[rx]=ry;↵
}↵
↵
void doit(int l,int r,int w)↵
{↵
if(l==r) return;↵
int tp=top;↵
int mid=l+r>>1;↵
for(int i=r;i>=mid+1;i--)↵
for(auto t:vec[i]) merge(t.first,t.second,w);↵
doit(l,mid,w);↵
while(top>tp) pop();↵
for(int i=l;i<=mid;i++)↵
{↵
if(!vec[i].empty()&&w==i) w++;↵
for(auto t:vec[i]) merge(t.first,t.second,w);↵
}↵
doit(mid+1,r,w);↵
while(top>tp) pop();↵
}↵
↵
inline void slove()↵
{↵
cin>>n>>m>>k;↵
for(int i=0;i<=m;i++) vec[i].clear();↵
for(int i=1,x,y,w;i<=m;i++) cin>>x>>y>>w,vec[w].emplace_back(x,y);↵
vector<int> tmp;↵
for(int i=1,x;i<=k;i++) cin>>x,tmp.push_back(x);↵
sort(tmp.begin(),tmp.end());↵
tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());↵
k=tmp.size();↵
for(int i=1;i<=n;i++) pt[i]=0;↵
for(int i=0;i<k;i++) pt[tmp[i]]=i+1;↵
for(int i=1;i<=n;i++) fa[i]=i,hei[i]=1;↵
for(int i=1;i<=k;i++) fa2[i]=i;↵
ans=0;↵
doit(0,m,0);↵
for(int i=1;i<=k;i++) if(fnd2(i)!=fnd2(1)) return cout<<"-1\n",void();↵
cout<<ans<<'\n';↵
}↵
↵
int main()↵
{↵
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);↵
int T;↵
cin>>T;↵
while(T-->0) slove();↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2222G]↵
↵
Author: [user:Lyz09,2026-04-26]↵
Developer: [user:Z-301,2026-04-26]↵
↵
<spoiler summary="Hint 1">↵
What is the value of a path that passes through the centroid of a tree?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
What is the value of a path that does not pass through the centroid of a tree?↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
This is a convolution problem. Enumerate only the terms in the polynomial with non-zero coefficients and prove that the time complexity is correct.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2222G]↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
#include <algorithm>↵
#include <cstring>↵
#include <cstdio>↵
#include <vector>↵
#include <queue>↵
using namespace std;↵
typedef long long ll;↵
typedef vector<int> vi;↵
class edge{↵
public:↵
edge(int x, int y, int z, int zz){v = x, w = y, c = z, nxt = zz;}↵
int v, w, c, nxt;↵
};↵
class graph{↵
private:↵
vector<int> head;vector<edge> e;↵
public:↵
void init(int n){head.clear(), e.clear();for (int i = 0;i <= n;i ++) head.emplace_back(-1);}↵
graph(){}graph(int n){init(n);}↵
inline int addedge(int u, int v, int w = 0, int c = 0){e.emplace_back(v, w, c, head[u]), head[u] = e.size() - 1;return e.size() - 1;}↵
inline int add2edge(int u, int v, int w = 0){int tmp = addedge(u, v, w);addedge(v, u, w);return tmp;}↵
inline int addfedge(int u, int v, int w, int c = 0){int tmp = addedge(u, v, w, c);addedge(v, u, 0, -c);return tmp;}↵
inline int& h(int u){return head[u];}↵
inline edge& operator[](int i){return e[i];}↵
}G;↵
const int N = 100005;ll ans[N];vi a[N];vector<ll> b[N];↵
int t, n, al, mns, rt, sz[N], cnt[N];↵
void dfs(int u, int fa){int mx = 0;sz[u] = 1;↵
for (int i = G.h(u);i != -1;i = G[i].nxt){↵
int v = G[i].v;if (v == fa) continue;↵
dfs(v, u), sz[u] += sz[v], mx = max(mx, sz[v]);↵
}mx = max(mx, al - sz[u]);↵
if (mx < mns) rt = u, mns = mx;↵
}↵
void dfs1(int u, int fa, int mx, int rt){↵
a[rt].push_back(max(mx, sz[u]));↵
for (int i = G.h(u);i != -1;i = G[i].nxt){↵
int v = G[i].v;if (v == fa) continue;↵
dfs1(v, u, max(mx, sz[u] - sz[v]), rt);↵
}↵
}↵
void calc(vi& a, vector<ll>& s, vi& b, int o){↵
int p = upper_bound(a.begin(), a.end(), o) - a.begin();↵
for (int i = 0, j;i < b.size();i ++){↵
j = upper_bound(a.begin(), a.end(), b[i]) - a.begin();↵
if (b[i] > o) ans[o] -= j, ans[b[i]] += j;j = max(j, p);↵
if (j < a.size()) ans[o] -= a.size() - j, s[j] ++;↵
}↵
}↵
void dfs2(int u, int fa){vi vc;↵
for (int i = G.h(u);i != -1;i = G[i].nxt){↵
int v = G[i].v, w = sz[v];if (v == fa) continue;↵
ans[n - w - w] += 1ll * cnt[w] * w, cnt[w] += w, vc.push_back(w);↵
}sort(vc.begin(), vc.end()), vc.erase(unique(vc.begin(), vc.end()), vc.end());↵
for (int x : vc) for (int y : vc) if (x < y)↵
ans[n - x - y] += 1ll * cnt[x] * cnt[y];↵
for (int v : vc) ans[n - v] += (u != rt) * cnt[v], cnt[v] = 0;↵
for (int i = G.h(u);i != -1;i = G[i].nxt){↵
int v = G[i].v;if (v != fa) dfs2(v, u);}↵
}↵
void solve(int u){vi to;↵
for (int i = G.h(u);i != -1;i = G[i].nxt){↵
int v = G[i].v;to.push_back(v), dfs1(v, u, 0, v);↵
sort(a[v].begin(), a[v].end()), b[v].resize(a[v].size(), 0);↵
}↵
for (int x : to) if (sz[x] * 3 >= n) for (int y : to) if (x < y || sz[y] * 3 < n) calc(a[x], b[x], a[y], n - sz[x] - sz[y]);↵
for (int v : to){ll ls = 0;↵
for (ll& x : b[v]) ls = x += ls;↵
for (int i = 0;i < a[v].size();i ++)↵
ans[max(a[v][i], n - sz[v])] ++,↵
ans[a[v][i]] += b[v][i];a[v].clear(), b[v].clear();↵
}dfs2(rt, 0);↵
}↵
int main(){scanf("%d", &t);↵
while (t --){scanf("%d", &n), G.init(n);↵
for (int i = n - 1, u, v;i --;)↵
scanf("%d%d", &u, &v), G.add2edge(u, v);memset(ans, 0, n + 1 << 3);↵
al = n, mns = N, dfs(1, 0), dfs(rt, 0), solve(rt), ans[n] += n;↵
for (int i = 1;i <= n;i ++) printf("%lld ", ans[i]);putchar('\n');↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2222H]↵
↵
Author: [user:CutieSmileHaruka,2026-04-26]↵
↵
<spoiler summary="Hint 1">↵
You are given an array $a$. How to count the number of arrays $b$ that satisfy $f(b) = a$ and $ \forall 1 \le i \le n, b_i \le r_i $.?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
You are given an array $a$. How to count the number of arrays $b$ that satisfy $f(f(b)) = a$ and $ \forall 1 \le i \le n, b_i \le r_i $.?↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
How many arrays $a$ satisfy there exists an array $b$ such that $f(f(b)) = a$?↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
[The partition numbers](https://oeis.org/A000041).↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2222H]↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
// 全身全霊！MORE MORE JUMP!!↵
#include <algorithm>↵
#include <cstring>↵
#include <cstdio>↵
#include <vector>↵
#include <queue>↵
#define mod 998244353↵
using namespace std;↵
typedef __int128_t lll;↵
template<typename T, const int M>↵
struct BHasher{inline int operator()(T x){return x % M;}};↵
template<typename T1, typename T2, int M, typename Hsr = BHasher<T1, M>>↵
struct HashMap{↵
struct node{int nx;T1 ky;T2 vl;};↵
int h[M];vector<node> nd;Hsr hsh;↵
HashMap(){memset(h, -1, sizeof(h));}↵
void clear(){memset(h, -1, sizeof(h)), nd.clear();}↵
inline bool find(T1 k){int p = hsh(k);↵
for (int i = h[p];i != -1;i = nd[i].nx)↵
if (nd[i].ky == k) return 1;return 0;↵
}↵
inline T2& operator[](T1 k){int p = hsh(k);↵
for (int i = h[p];i != -1;i = nd[i].nx)↵
if (nd[i].ky == k) return nd[i].vl;↵
nd.push_back((node){h[p], k, T2()});↵
return nd[h[p] = nd.size() - 1].vl;↵
}↵
};↵
const int N = 55, K = 1005, M = 1296000;HashMap<lll, int, 1919839> id;↵
int t, n, m, k, c, a[N], fa[M], to[M][N], C[N][N], f[M], ans[K], rt, cnt;↵
unsigned char b[M][N], bb[N], ps[M][N], sk[N], tmp[N], sm[M], ct[M], dep[M];↵
void dfs(int p, int sm){↵
if (p > n){m ++;↵
memcpy(ps[m], sk, sizeof(sk));↵
memcpy(b[m], bb, sizeof(bb));↵
return;↵
}↵
for (int x = 0;x <= n && sm <= n;x ++, sm += p){↵
if (x) sk[++ c] = p;↵
bb[p] = x, dfs(p + 1, sm);↵
if (x) sk[c --] = 0;↵
}↵
}↵
inline lll hsh(unsigned char* A){lll st = 0;↵
for (int i = 1;i <= n;i ++)↵
st <<= 1, st |= 1, st <<= A[i];return st;↵
}↵
inline unsigned char gdep(int x){return dep[x] ? dep[x] : dep[x] = gdep(fa[x]) + 1;}↵
inline void add(int& x, int y){x += y;if (x >= mod) x -= mod;}↵
int main(){scanf("%d", &t), n = N - 5;↵
for (int i = 0;i <= n;i ++){C[i][0] = 1;↵
for (int j = 1;j <= i;j ++) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;}↵
while (t --){scanf("%d%d", &n, &k), m = cnt = 0, dfs(1, 0);↵
memset(dep, 0, m + 1 << 1), memset(f, 0, m + 1 << 2), memset(ans, 0, k + 1 << 2);↵
for (int i = 1;i <= n;i ++) scanf("%d", &a[i]);↵
for (int i = 1;i <= m;i ++){↵
lll st = hsh(b[i]);id[st] = i;↵
for (int j = n, p = -1;j >= 1;j --){↵
p += b[i][j] + 1;if (b[i][j])↵
to[i][j] = id[((st >> p) << p - 1) | (st & ((lll)1 << p) - 1)];↵
}↵
}↵
for (int i = 1;i <= m;i ++){↵
memset(tmp, 0, sizeof(tmp)), sm[i] = ct[i] = 0;↵
for (int j = 1;j <= n;j ++)↵
tmp[b[i][j]] ++, sm[i] += j * b[i][j], ct[i] += b[i][j];↵
if (sm[i] == 1) rt = i;↵
fa[i] = id[hsh(tmp)];↵
}f[1] = dep[1] = dep[rt] = 1;↵
for (int i = n, ss = 0;i >= 1;i --){↵
for (int o = 1;o <= n;o ++) ss += a[o] == i;↵
for (int j = m;j >= 1;j --)↵
if (ct[j] <= n - i + 1 && sm[j] <= ss)↵
for (int k = 1, x, now;ps[j][k];k ++)↵
if (now = f[to[j][x = ps[j][k]]])↵
f[j] = (f[j] + 1ll * now * C[ss - sm[j] + x][x]) % mod;↵
}↵
for (int i = 2;i <= m;i ++) add(ans[gdep(i) + 2], f[i]);↵
for (int i = 1;i <= n;i ++) cnt += a[i] > 0;↵
add(ans[3], mod - cnt), add(ans[2], cnt - (a[1] > 0)), add(ans[1], 1 + (a[1] > 0));↵
for (int i = 1;i <= k;i ++) printf("%d ", ans[i]);putchar('\n');↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
