@[kkkfc0114514](/user/935377)
大佬在看不见的地方还在卷题%%%
by ycyxh1 @ 2024-09-28 13:00:36
@[ycyxh1](/user/1287433) so到底怎么做啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊
by kkkfc0114514 @ 2024-09-28 13:01:55
ok调出来了因为树是无向图而上面的代码只处理了一个方向，附AC code:
```cpp
#include <bits/stdc++.h>
namespace SXL {
using std::vector;
using std::array;
using std::max;
constexpr int MAXN = 100005;
vector<array<int,2>> edge[MAXN];
int nt[MAXN];
int id,maxx,l,r,ans;
int dis[MAXN];
int father[MAXN];
void dfs(int x,int fa,int step) {
if(step >= maxx) {
id = x;
maxx = step;
}
for(int i = 0;i < (int)edge[x].size();i++) {
if(edge[x][i][0] == fa) {
father[x] = i;
continue;
}
dfs(edge[x][i][0],x,step + 1);
}
}
bool dfsToChange(int x,int fa,int tar) {
if(x == tar) {
return true;
}
for(int i = 0;i < (int)edge[x].size();i++) {
if(edge[x][i][0] == fa) continue;
if(dfsToChange(edge[x][i][0],x,tar)) {
nt[x] = i;
return true;
}
}
return false;
}
int solve1() {
dfs(1,0,0);
r = id;
maxx = 0;
dfs(r,0,0);
l = id;
dfsToChange(r,0,l);
for(int i = r;i != l;i = edge[i][nt[i]][0]) {
edge[i][nt[i]][1] = -1;
}
for(int i = l;i != r;i = edge[i][father[i]][0]) {
edge[i][father[i]][1] = -1;
}
return maxx;
}
void solve2(int x,int fa) {
for(auto i : edge[x]) {
if(i[0] == fa) {
continue;
}
solve2(i[0],x);
ans = max(ans,dis[x] + dis[i[0]] + i[1]);
dis[x] = max(dis[x],dis[i[0]] + i[1]);
}
}
void main() {
int n,k;
scanf("%d%d",&n,&k);
for(int i = 1,a,b;i < n;i++) {
scanf("%d%d",&a,&b);
edge[a].push_back({b,1});
edge[b].push_back({a,1});
}
if(k == 1) {
solve2(1,0);
printf("%d\n",2 * n - ans - 1);
} else {
int l1 = solve1();
solve2(1,0);
printf("%d\n",2 * n - l1 - ans);
}
}
}
int main() {
SXL::main();
return 0;
}
```
by kkkfc0114514 @ 2024-09-28 14:52:24