A 一般图最小匹配
首先排完序后肯定选连续两个。直接 DP，\(f_{i,j}\) 就是表面意思，\(f_{i,j}=min(f_{i-1,j},f_{i-2,j-1}+a_i-a_i-2)\)。
差分后发现问题转化成了选择的数不能相邻，这时候也可以直接考虑 DP，但是这是一个经典的反悔贪心。
记下 \(pre\) 和 \(nex\)，直接扔到堆里，选择一个策略后，将他和两边的点看成一个整体，这就是反悔策略，再更新相关 \(pre\) 和 \(nex\)，扔到堆里。
#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=5e3+10,inf=1e18;
struct VAL{int id,w;bool operator<(const VAL &b)const{return w>b.w;}
};
int n,m,a[N],d[N],pre[N],suc[N],ans;
bool vis[N];
std::priority_queue<VAL> q;
signed main(){freopen("match.in","r",stdin);freopen("match.out","w",stdout);// freopen("in.in","r",stdin);freopen("out.out","w",stdout);std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);n=read();m=read();a[0]=-inf;fo(i,1,n)a[i]=read();std::sort(a+1,a+n+1);for(int i=1;i<n;++i)d[i]=a[i+1]-a[i],pre[i]=i-1,suc[i]=i+1;suc[n-1]=0;for(int i=1;i<n;++i)q.push({i,d[i]});for(int i=1;i<=m;++i){while(vis[q.top().id])q.pop();auto it=q.top();q.pop();ans+=it.w;int id=it.id;int l=pre[id],r=suc[id];vis[l]=vis[r]=1;pre[id]=pre[l],suc[pre[l]]=id;suc[id]=suc[r],pre[suc[r]]=id;d[id]=(l&&r)?std::min(d[l]+d[r]-d[id],inf):inf;q.push({id,d[id]});}std::cout<<ans<<'\n';
}
B 重定向
纯贪心，5k 的思路很清楚。
扫描每个位置有如下情况：
- 当前位是 \(0\)，比较后缀最小和最小没出现的数，如果前者更小，删除那个位置填到这个位置上。否则填没出现的数，继续扫描。
- 当前位不是 \(0\)，比较他和他的下一位，下一位是 \(0\) 就比较最小没出现的数，如果大于就删这个位置，否则继续扫描。
最后直接填数即可。
C 斯坦纳树
做法较多，第一种：简单手玩发现，每次加点都是向已经遍历过的点集连，连到的第一个存在就正确，否则不正确，直接把第一个数钦定为根后就相当于直接往上找了。每次暴力跳就行，时间复杂度 \(\mathcal{O}(n)\)。
第二种：考虑牛牛什么时候正确，当且仅当任意两点 LCA 都在点集中时正确，但是会有特殊情况，所以直接把第一个数钦定为根，这时结论就完全正确了。发现这个就是虚树上的点集，拿 set 维护，如果虚树点集大小和当前点集大小相同就正确。时间复杂度 \(\mathcal{O}(n\log n)\)。
第三种：考虑倒着删点，手玩发现，当三个度的点删去后是不合法的，转化成了虚点，否则是没有影响的，所以每删去一个点就查看与它的度，如果不小于 \(3\)，它转化为虚点，否则真正删去，相连的点度数减减，看看有没有还能真正删去的点，拿队列存一下后扩展即可。时间复杂度 \(\mathcal{O}(n)\)。
以上三种情况，都需要根据 \(0\) 的边权进行缩点或维护连通块操作，贴一下做法三的代码。
如果区间询问咋办，回滚莫队，只删不增，考虑拿链表维护，但是感觉有 log 做法啊，有没有大神能看看。
#include<bits/stdc++.h>
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=3e5+10;
int n,r[N],a[N],num[N],d[N],pd,fa[N];
bool ans[N];
struct EDGE{int u,v;}E[N];
std::vector<int> e[N];
bool vis[N],ne[N],mp[N];
inline int find(int x){return r[x]==x?x:r[x]=find(r[x]);}
std::queue<int> q;
signed main(){freopen("tree.in","r",stdin);freopen("tree.out","w",stdout);// freopen("in.in","r",stdin);freopen("out.out","w",stdout);std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);int n=read();for(int i=1;i<=n;++i)r[i]=i;for(int i=1;i<n;++i){ int u=read(),v=read(),w=read();E[i]={u,v};if(!w)r[find(u)]=find(v);}for(int i=1;i<=n;++i)r[i]=find(i);for(int i=1;i<n;++i){int u=r[E[i].u],v=r[E[i].v];if(u==v)continue;e[u].emplace_back(v);e[v].emplace_back(u);d[u]++,d[v]++;}for(int i=1;i<=n;++i)a[i]=r[read()],num[a[i]]++;for(int i=n;i;--i){ans[i]=!pd;num[a[i]]--;if(num[a[i]])continue;pd++;if(d[a[i]]<=2){q.push(a[i]);while(!q.empty()){int x=q.front();q.pop();vis[x]=1;pd--;int tep[2]={0},zc=-1;for(int v:e[x]){if(vis[v])continue;tep[++zc]=v;d[v]--;}if(zc==1)e[tep[0]].emplace_back(tep[1]),e[tep[1]].emplace_back(tep[0]),d[tep[0]]++,d[tep[1]]++;for(int i=0;i<=zc;++i){if(d[tep[i]]<=2&&!num[tep[i]])q.push(tep[i]);}}}}for(int i=1;i<=n;++i)std::cout<<ans[i];
}
D 直径
超级计数 DP 题，不会。
总结
这场也是打出了退役水平，T1 你不会裸 DP，不会反悔贪心，还不会差分吗，推出来性质之后就不能再想想之前的思路。T2 就是最简单的贪心也打俩小时，T3 什么都想到了，钦定根没想到，鉴定为：机房垫底水平。大家都在进步。四个小时只有一个小时在拿分，简单场困难场在我这里根本没什么区别，再打成这样退役就板上钉钉了。
