Link:https://www.lydsy.com/JudgeOnline/problem.php?id=1912
Algorithm:
K=0：res=（n-1）*2 每条边恰好走2遍
K=1：res=res-树上最长链+1
由于每形成环，环上的边对答案的贡献都会-1，因此只要将树上最长链连成环即可
K=2：res=res-树上当前最长链+1
将原树上直径的边的边权赋为-1，表示如果原直径边同时出现在第2个环时对答案贡献增加1（变为2）
证明：第二次求最长链相当于对第一次的“反悔”操作，重复的边表示没有变化
相当于是把两条交错的最长链变成了两条分开的链，其和必然是不交错的两条链中最大的（否则可以用最长链代替）
Code:
#include <bits/stdc++.h> using namespace std; inline int read()
{
char ch;int num,f=;
while(!isdigit(ch=getchar())) f|=(ch=='-');
num=ch-'';
while(isdigit(ch=getchar())) num=num*+ch-'';
return f?-num:num;
} const int MAXN=1e5+;
int n,k,ch[MAXN][],mx[MAXN][],mx_node,dia,res=; struct edge
{
int to,nxt,val;
}G[MAXN*];
int head[MAXN],cnt=; void add_edge(int u,int v)
{
G[++cnt].to=v;G[cnt].nxt=head[u];head[u]=cnt;G[cnt].val=;
} void dfs(int u,int anc) //一遍dfs求树的直径
{
mx[u][]=mx[u][]=;
for(int i=head[u];i;i=G[i].nxt)
{
int v=G[i].to;
if(v==anc) continue;
dfs(v,u);
if(mx[u][]<mx[v][]+G[i].val)
{
mx[u][]=mx[u][],mx[u][]=mx[v][]+G[i].val;
ch[u][]=ch[u][],ch[u][]=i;
}
else if(mx[u][]<mx[v][]+G[i].val)
mx[u][]=mx[v][]+G[i].val,ch[u][]=i;
} if(mx[u][]+mx[u][]>dia)
dia=mx[u][]+mx[u][],mx_node=u;
} int main()
{
n=read();k=read();
for(int i=;i<n;i++)
{
int x=read(),y=read();
add_edge(x,y);add_edge(y,x);
} dfs(,);res=*(n-)-dia+;
if(k==) return cout << res,;
for(int i=ch[mx_node][];i;i=ch[G[i].to][]) G[i].val=G[i^].val=-;
for(int i=ch[mx_node][];i;i=ch[G[i].to][]) G[i].val=G[i^].val=-;
dia=;dfs(,);res=res-dia+; cout << res; return ;
}
Review:
1、树的直径的求法
以前只会双dfs法
其实可以一遍dfs，
使用记录最长子链和次长子链的方法，如果存在最长“父链”比次长子链大的情况，其会被包含在祖先的情况中
Resources:https://blog.csdn.net/ilsswfr/article/details/52078089
2、如果对无向边有修改操作，用链式前向星记录
因为正反向边的序号相邻，可以一起更新
3、求解高维度问题时（k个不相交链的最大长度和），
可以采取贪心求解每个子问题（当前最长链） + 构建反悔机制（走完后边权赋为-1）来解决问题