胜兵必骄 wars
称 \(a=1\) 为黑色，否则为白色。
注意到一次战斗本质是交换颜色，一条边被操作两次不会对颜色产生影响。最初的想法是找到一个黑点 \(u\)，与白色儿子交换颜色，递归到子树处理；同色的儿子提前递归，回溯时趁 \(u\) 还没从白色变回黑色时连做两次。
这样会有一些问题，如果一个点的所有儿子都与他同色，那么这个点必须得被提前反色。设 \(f_{u,0/1}\) 表示 \(u\) 颜色为 \(0/1\) 时能否被操作以及此时的构造。从一个有不同色相邻点的点开始 dfs，做树上 DP 即可。
证明一下为什么两种颜色点均存在时一定有解，找到树上一条两端不同色的边，分成两个子问题，如果某一侧颜色全相同，在当前边两次操作之间做，否则在操作之前做，一定有解。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
typedef pair<ll,ll> pll;
template<typename T>
void chkmin(T &x,const T &y){x=min(x,y);}
template<typename T>
void chkmax(T &x,const T &y){x=max(x,y);}
const int inf=0x3f3f3f3f;
const ll infll=0x3f3f3f3f3f3f3f3f;
const int MOD=998244353;
void add(int &x,int y){x+=y;if(x>=MOD) x-=MOD;
}
int qpow(int a,ll b){int mul=1;while(b){if(b&1) mul=(ll)mul*a%MOD;a=(ll)a*a%MOD;b>>=1;}return mul;
}
const int N=1000005;
int n,a[N],f[N][2],vis[N];
vector<int> G[N];
vector<pii> vec[N][2];
void dfs(int u,int fa){int cnt[2];cnt[0]=cnt[1]=0;for(auto v:G[u]){if(v==fa) continue;dfs(v,u);cnt[a[v]]++;}if(cnt[0]+cnt[1]==0){f[u][0]=f[u][1]=1;return;}for(int c=0;c<2;c++){if(cnt[c^1]){f[u][c]=1;for(auto v:G[u]){if(v==fa) continue;if(f[v][a[v]]) vec[u][c].push_back({-1,v});}for(auto v:G[u]){if(v==fa) continue;if(a[v]^c){vec[u][c].push_back({u,v});if(!f[v][a[v]]) vec[u][c].push_back({-1,v});vec[u][c].push_back({u,v});}}int vv=vec[u][c].back().second;vec[u][c].pop_back();for(auto v:G[u]){if(v==fa) continue;if(!(a[v]^c)){vec[u][c].push_back({u,v});if(!f[v][a[v]]) vec[u][c].push_back({-1,v});vec[u][c].push_back({u,v});}}vec[u][c].push_back({u,vv});}else f[u][c]=0;}
}
void dfs2(int u,int c){for(auto [x,y]:vec[u][c]){if(x==-1) dfs2(y,a[y]);else printf("%d %d\n",x,y),a[y]^=1;}
}
void __INIT__(){}
void __SOLVE__(){scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);G[u].push_back(v),G[v].push_back(u);}for(int i=1;i<=n;i++){bool flag=false;for(auto j:G[i]) if(a[i]!=a[j]){flag=true;break;}if(flag){dfs(i,i);dfs2(i,a[i]);return;}}
}
int main(){#ifndef JZQfreopen("wars.in","r",stdin);freopen("wars.out","w",stdout);#endifint T=1;// scanf("%d",&T);__INIT__();while(T--) __SOLVE__();return 0;
}
数据恢复 recovery
观察性质。
考虑做判定。
*观察 1
对于非前缀最大值且不固定的位置，其目标顺序应递增。
否则，可以调整出字典序更小的方案。
观察 2
对于一个前缀最大值位置 \(i\)，设 \(mx_i=\max\limits_{\substack{pre_i\le j<nxt_i \\ i\neq j}}\{a'_j\}\)，则 \(i\) 不能被替换当且仅当 \((mx_i,a'_i]\) 中的数被固定。
笔者考场仅观察到了更弱的结论（必要不充分条件）。
必要性显然，直接调整。
充分性证明，从左往右固定每一个前缀最大值，如果 \(i\) 被替换，则 \(i\) 被移至 \(nxt_i\) 后，必然有一个 \(nxt_i\) 后的数要移进 \(i\sim nxt_i\)，根据观察 1，这就会导致产生新的前缀最大值。
综上，一个方案合法当且仅当不被固定的非前缀最大值递增，不被固定的前缀最大值满足 \((mx_i,a'_i]\) 被固定。
考虑在值域上 DP，设 \(f_i\) 表示考虑了 \(1\sim i\) 的非前缀最大值，且 \(i\) 不被固定的方案数。
暴力的转移为：
\[f_i=\sum_{\substack{j<i \\ p_j<p_i}}f_j2^{cnt_{j+1,i-1}},\ c_{p_i}=0
\]
其中 \(cnt_{l,r}\) 表示被 \([l,r]\) 完全包含的 \((mx_i,a'_i]\) 数量。
用前缀和维护 \(cnt\)，用树状数组维护 \(f\)，即可 \(\mathcal{O}(n\log n)\)。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
typedef pair<ll,ll> pll;
template<typename T>
void chkmin(T &x,const T &y){x=min(x,y);}
template<typename T>
void chkmax(T &x,const T &y){x=max(x,y);}
const int inf=0x3f3f3f3f;
const ll infll=0x3f3f3f3f3f3f3f3f;
const int MOD=998244353,INV2=(MOD+1)>>1;
void add(int &x,int y){x+=y;if(x>=MOD) x-=MOD;
}
int qpow(int a,ll b){int mul=1;while(b){if(b&1) mul=(ll)mul*a%MOD;a=(ll)a*a%MOD;b>>=1;}return mul;
}
const int N=1000005;
int n,a[N],p[N],nxt[N],c[N],pre[N],cnt[N],pw[N],invpw[N];
int val[N],tr[N],f[N];
#define lowbit(x) ((x)&(-(x)))
void modify(int x,int v){add(val[x],v);for(;x<=n+1;x+=lowbit(x)) add(tr[x],v);
}
void change(int x,int v){int d=v-val[x];if(d<0) d+=MOD;modify(x,d);
}
int query(int x){int sum=0;for(;x;x-=lowbit(x)) add(sum,tr[x]);return sum;
}
int query(int l,int r){int s=query(r)-query(l-1);if(s<0) s+=MOD;return s;
}
void __INIT__(){pw[0]=invpw[0]=1;for(int i=1;i<N;i++){pw[i]=(pw[i-1]<<1)%MOD;invpw[i]=(ll)INV2*invpw[i-1]%MOD;}
}
void __SOLVE__(){scanf("%d",&n);int mx=0,lst=0;for(int i=1;i<=n;i++){scanf("%d",&a[i]);p[a[i]]=i;if(a[i]>mx){nxt[lst]=i,pre[i]=lst;mx=a[i],lst=i,c[i]=1;}else c[i]=0;}nxt[lst]=n+1;vector<pii> vec;a[0]=0;for(int i=1;i<=n;i++){if(!c[i]) continue;int mx=a[pre[i]];for(int j=i+1;j<nxt[i];j++) chkmax(mx,a[j]);vec.push_back({mx+1,a[i]});}for(int i=1;i<=n;i++) cnt[i]=0;for(int i=1,j=0;i<=n;i++){if(i>vec[j].second) j++;if(j<vec.size()&&i==vec[j].first) cnt[i]=1;cnt[i]+=cnt[i-1];if(j>=vec.size()||i<vec[j].first) pre[i]=i;else pre[i]=vec[j].first-1;}// for(int i=1;i<=n;i++) printf("%d ",cnt[i]);// printf("\n");for(int i=1;i<=n+1;i++) val[i]=tr[i]=0;modify(1,1);for(int i=1,j=0;i<=n;i++){if(j<vec.size()&&i>vec[j].second){for(int k=vec[j].first;k<=vec[j].second;k++) change(p[k]+1,(ll)INV2*val[p[k]+1]%MOD);j++;}if(c[p[i]]) continue;f[i]=(ll)pw[cnt[pre[i]]]*query(p[i]+1)%MOD;modify(p[i]+1,(ll)invpw[cnt[pre[i]]]*f[i]%MOD);}// for(int i=1;i<=n;i++) printf("%d ",f[i]);// printf("\n");printf("%lld\n",(ll)pw[vec.size()]*query(n+1)%MOD);
}
int main(){#ifndef JZQfreopen("recovery.in","r",stdin);freopen("recovery.out","w",stdout);#endifint T=1;scanf("%*d%d",&T);__INIT__();while(T--) __SOLVE__();return 0;
}