更新日志
概念
图上最小点定连通块，就是给出无向连通图上一些点，要求找出边权和最小的连通分量使这些点强连通。
现在要求这个连通块内的边权之和。
思路
先给出结论：把节点按照dfs序排序，统计所有相邻的节点以及起始点与末尾点之间的距离，将它们求和，所求的答案即为这个和除以2。
感性证明一下，可以想象一个人（或者蚂蚁，或者飞船，或者任何能沿着路走的生物，或者不是生物也行），在dfs生成树上走上、走下，依次走向每一个节点，最后走会原点，不难想象到每一条边都被他走了两遍。
稍微理性一点的话，因为是按照dfs序依次排列的，就有几种情况：
- 一点是另一点的祖先节点，直接走下去。
- 二者属于不同子树，先走回到公共祖先节点（必然是之前已经经过的节点），再走进一条新的路径
重复二个操作，那么都是先走到最深的节点，再回溯到某个点，再沿着另一个路径搜索……最后回到起始点，每条边就都被走了两次。
例题
代码
前注：非题解，不做详细讲解
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,T=32;
int n,k;
int ans;
int distal;
vector<int> vs[N];
set<int> dst;
int dp[N];
int f[N][T+5];
void brinit(){
for(int t=1;t<=T;t++){
for(int i=1;i<=n;i++){
f[i][t]=f[f[i][t-1]][t-1];
}
}
}
int lca(int a,int b){
if(dp[a]>dp[b])swap(a,b);
for(int t=T;t>=0;t--){
if(dp[f[b][t]]>=dp[a])b=f[b][t];
}
if(a==b)return a;
for(int t=T;t>=0;t--){
if(f[a][t]!=f[b][t]){
a=f[a][t];
b=f[b][t];
}
}
return f[a][0];
}
int dis(int a,int b){
int c=lca(a,b);
return dp[a]-dp[c]+dp[b]-dp[c];
}
int cnt;
int dfn[N];
void dfs(int now,int fa){
dfn[now]=++cnt;
f[dfn[now]][0]=dfn[fa];
dp[dfn[now]]=dp[dfn[fa]]+1;
for(auto nxt:vs[now]){
if(nxt==fa)continue;
dfs(nxt,now);
}
}
void pushin(int x){
dst.insert(dfn[x]);
int now,lst,nxt;
now=lst=nxt=0;
auto plc=dst.lower_bound(dfn[x]);
now=*plc;
auto lstp=plc;
if(lstp==dst.begin())lst=*dst.rbegin();
else{advance(lstp,-1);lst=*lstp;}
auto nxtp=plc;advance(nxtp,1);
if(nxtp==dst.end())nxt=*dst.begin();
else nxt=*nxtp;
distal-=dis(lst,nxt);
distal+=dis(lst,now);
distal+=dis(now,nxt);
}
void throut(int x){
int now,lst,nxt;
now=lst=nxt=0;
auto plc=dst.lower_bound(dfn[x]);
now=*plc;
auto lstp=plc;
if(lstp==dst.begin())lst=*dst.rbegin();
else{advance(lstp,-1);lst=*lstp;}
auto nxtp=plc;advance(nxtp,1);
if(nxtp==dst.end())nxt=*dst.begin();
else nxt=*nxtp;
distal+=dis(lst,nxt);
distal-=dis(lst,now);
distal-=dis(now,nxt);
dst.erase(dfn[x]);
}
inline bool check(){
return distal/2+1<=k;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>k;
int a,b;
for(int i=1;i<n;i++){
cin>>a>>b;
vs[a].push_back(b);
vs[b].push_back(a);
}
dfs(1,1);
brinit();
for(int i=0,j=1;i<=n;pushin(++i)){
while(!check()){
throut(j++);
}
ans=max(ans,i-j+1);
}
cout<<ans;
return 0;
}