A score and rank
神秘贪心，如果全是正数，每当大于等于 \(S\) 时删除最大的最优。如果 \(S\) 是负数，删去所有大于等于的数就是答案。
思考删除最大的为什么不对，会有这样的情况，一个负数很小，使得选择区间改变，导致维护的集合清空。这时可以选择拿正数来抵消负数。
具体来说，当前 \(sum\) 加上 \(x\) 后如果小于等于 \(0\) 直接清空，重新选择，否则不断拿当前集合中最小的数来抵消这个负数，贪心保证以后的删除仍然去删大数，拿 std::multiset 维护即可。
B HZOI大作战
维护单调栈卡空间，过不了。直接预处理出从每个点跳到根要更换多少次，再倍增求出大于当前数的位置，再减去第一个在祖先之上大于路径 \(max\) 的位置的次数即可。
C Delov的旅行
最大值最小，考虑二分答案，按 dfs 序遍历一定不劣，发现对于每棵子树，只有进去的第一个叶子和最后一个叶子返回会对外界产生影响，考虑设 \(f_{u,i,j}\) 表示在 \(u\) 的子树内，前往的第一个叶子距离是 \(i\)，最后一个叶子的距离是 \(j\)，中间的代价是否都小于等于 \(mid\)，状态数爆炸，但是对于 \(i_1\le i_2,j_1\le j_2\)，\((i_2,j_2)\) 是没有用处的，因为有比他更优且可行的方案，所以总状态数只有叶子个。
所以随着 \(i\) 的增大，\(j\) 一定变小，用 set 维护状态，因为有上述单调性，合并子树可以直接双指针，在满足中间条件的同时尽量选择回来代价小的，所以我们找到最大的 \(i\) 即可。注意第一天去和第二天回可以不满足限制。
#include<bits/stdc++.h>
#define int long long
#define fo(i,s,t) for(int i=s;i<=t;++i)
typedef long long ll;
typedef unsigned long long ull;
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=1.5e5;
int n;
struct EDGE{int v,w;};
std::vector<EDGE> e[N];
struct NODE{
int a,b;
friend bool operator<(const NODE &a,const NODE &b){
return a.a==b.a?a.b<b.b:a.a<b.a;
}
}zc[N];
std::set<NODE> s[N];
inline bool dfs(int x,int fa,int mid){
s[x].clear();
int ls=0,rs=0,vl,vr;
for(auto it:e[x]){
int v=it.v,w=it.w;if(v==fa)continue;
if(!dfs(v,x,mid))return 0;
if(ls)rs=v,vr=w;
else ls=v,vl=w;
}
if(!ls&&!rs){s[x].insert({0,0});return 1;}
int cnt=0;
auto it=s[rs].begin(),en=--s[rs].end();
for(auto now:s[ls]){
while(it!=en&&(*next(it)).a+now.b+vl+vr<=mid)++it;
if((*it).a+now.b+vl+vr<=mid)zc[++cnt]={now.a+vl,(*it).b+vr};
}
it=s[ls].begin(),en=--s[ls].end();
for(auto now:s[rs]){
while(it!=en&&(*next(it)).a+now.b+vl+vr<=mid)++it;
if((*it).a+now.b+vl+vr<=mid)zc[++cnt]={now.a+vr,(*it).b+vl};
}
if(!cnt)return 0;
std::sort(zc+1,zc+cnt+1);
s[x].insert(zc[1]);
int las=1;
for(int i=2;i<=cnt;++i)
if(zc[i].b<zc[las].b&&zc[i].a>zc[las].a)s[x].insert(zc[i]),las=i;
if(s[x].empty())return false;
return true;
}
signed main(){
freopen("trip.in","r",stdin);freopen("trip.out","w",stdout);
std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
n=read();
int l=0,r=0,res=0;
for(int i=2;i<=n;++i){
int u=read(),w=read();e[u].push_back({i,w});e[i].push_back({u,w});
r+=w;
}
while(l<=r){
int mid=l+r>>1;
if(dfs(1,0,mid))r=mid-1,res=mid;
else l=mid+1;
}
std::cout<<res<<'\n';
}
D gtm 和 joke的星球
斯坦纳树模板。
最后选出来的子图是一棵树，设 \(f_{i,S}\) 表示以 \(i\) 为根，联通 \(S\) 集合的最小代价，有两种情况的转移，一种是根的度数为 \(1\)，\(f_{i,S}=f_{j,S}+w(i,j)\)，另一种是不唯一，考虑拼接起来，有 \(f_{i,S}=f_{i,T}+f_{i,S-T}\)。
第一个转移和最短路的转移方程一样，最短路即可，第二种转移枚举子集即可，时间复杂度 \(\mathcal{O}(n3^k+n^22^k)\)。