D. Maximum Subarray
十分钟秒了一道 *2000，非常爽，但是个人感觉确实非常简单。
下面令 \(b_i=a_{i}-x\)，\(b_i'=a_i+x\) 。
因为 \(k<=20\)，因此考虑一个复杂度与 \(k\) 相关的做法。
不妨 dp：设 \(f_{i,j,0/1}\) 表示考虑了前 \(i\) 个数，对 \(j\) 个数加上了 \(x\)，第 \(i\) 个数不加/加，且强制选择第 \(i\) 个数的情况下的最大子段和。
转移是平凡的，就类似于正常的求最大子段和：
\[\begin{aligned} f_{i,j,0}&=\max(b_i,f_{i-1,j,0}+b_i,f_{i-1,j,1}+b_i) \\ f_{i,j,1}&=\max(b_i',f_{i-1,j-1,0}+b_i',f_{i-1,j-1,1}+b_i') \end{aligned} \]对所有满足 \(n-i\ge k-j\) 的 \(f_{i,j,0/1}\) 统计答案即可，实现时注意一些边界条件。
时间复杂度 \(O(nk)\)。
#include<bits/stdc++.h>
#define int long long
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rof(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int N=5e5+5;
int n,k,x,a[N],f[N][22][2];
void Main(){
cin>>n>>k>>x;
For(i,1,n) cin>>a[i];
int ans=0;
For(i,1,n) For(j,0,min(i,k)){
int a1=a[i]-x,a2=a[i]+x;
if(i!=j) f[i][j][0]=max({a1,f[i-1][j][0]+a1,f[i-1][j][1]+a1});
if(j) f[i][j][1]=max({a2,f[i-1][j-1][0]+a2,f[i-1][j-1][1]+a2});
if(n-i>=k-j) ans=max({ans,f[i][j][0],f[i][j][1]});
}
cout<<ans<<'\n';
For(i,1,n) For(j,0,k) f[i][j][0]=f[i][j][1]=0;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T=1;cin>>T;
while(T--) Main();
return 0;
}
E. Colored Subgraphs
看出来了换根 dp，但是完全不会实现。
我们不妨手模一下题目中对染色的限制条件，不难发现等价于以 \(r\) 为根时对树进行链剖分，代价为最短链的点数。
那么先考虑固定以 \(1\) 为根时怎么做，假设对于所有的儿子我们已经染好了色，那么贪心地想，我们肯定会把当前点染成儿子中长度最短的那个颜色，这样一定是最优的，而次小的以及更大的链长度就被定住了，此时会影响答案的就是当前点的儿子中次小的那个。
我们对每个点 \(u\) 维护一个 \(f_u\) 表示 \(u\) 的所有儿子所在的链的长度集合，那么答案即为所有 \(f_u\) 的次小值以及 \(f_1\) 的最小值加一之间的最小值。
考虑换根，将根从 \(u\) 换到 \(v\) 的过程其实就类似于，删除 \(v\) 对 \(f_u\) 的贡献，加入 \(u\) 对 \(f_v\) 的贡献，这个可以使用 multiset 简单维护，回溯的过程中及时撤销即可。
时间复杂度 \(O(n\log n)\)。
#include<bits/stdc++.h>
#define int long long
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rof(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int N=5e5+5;
const int inf=1e18;
int n,ans;
multiset<int>f[N],g;
vector<int>G[N];
int get(int now){
if(!f[now].size()) return 1;
return (*f[now].begin())+1;
}
void ins(int now,int val){
if(f[now].size()>=2) g.erase(g.find(*next(f[now].begin())));
f[now].insert(val);
if(f[now].size()>=2) g.insert(*next(f[now].begin()));
}
void del(int now,int val){
if(f[now].size()>=2) g.erase(g.find(*next(f[now].begin())));
f[now].erase(f[now].find(val));
if(f[now].size()>=2) g.insert(*next(f[now].begin()));
}
void dfs1(int now,int fa){
for(int to:G[now]){
if(to==fa) continue;
dfs1(to,now);
f[now].insert(get(to));
}
if(f[now].size()>=2) g.insert(*next(f[now].begin()));
}
void dfs2(int now,int fa){
ans=max(ans,min(get(now),g.empty()?inf:*g.begin()));
for(int to:G[now]){
if(to==fa) continue;
del(now,get(to));
ins(to,get(now));
dfs2(to,now);
del(to,get(now));
ins(now,get(to));
}
}
void Main(){
cin>>n;g.clear();ans=0;
For(i,1,n) f[i].clear(),G[i].clear();
For(i,1,n-1){
int u,v;cin>>u>>v;
G[u].emplace_back(v);
G[v].emplace_back(u);
}
dfs1(1,0);dfs2(1,0);
cout<<ans<<'\n';
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T=1;cin>>T;
while(T--) Main();
return 0;
}