Original link: https://www.shuizilong.com/house/archives/luogu-p3629-apio2010-%E5%B7%A1%E9%80%BB/
The advanced method of finding the diameter twice seems to be rotten. .
Here is a more conventional dp replacement. .
The method is that Two Paths can consider one more situation~~
#include <lastweapon/io>
using namespace lastweapon;
const int N = int(3e5) + 9;
int dn[N], up[N]; // Inner diameter of subtree, outer diameter of subtree int d[N][4], e[N]; // The longest distance of top4 within the subnumber, the longest distance outside the subtree long distance VI adj[N]; int n, K, z;
void upd(int d[], int v) {
if (v > d[0]) d[3] = d[2], d[2] = d[1], d[1] = d[0], d[0] = v;
else if (v > d[1]) d[3] = d[2], d[2] = d[1], d[1] = v;
else if (v > d[2]) d[3] = d[2], d[2] = v;
else if (v > d[3]) d[3] = v;
}
void dfs1(int u = 1, int p = 0) {
for (auto v: adj[u]) if (v != p) {
dfs1(v, u);
upd(d[u], d[v][0] + 1);
checkMax(dn[u], dn[v]);
}
checkMax(dn[u], d[u][0] + d[u][1]);
}
void dfs2(int u = 1, int p = 0) {
for (auto v: adj[u]) if (v != p) {
checkMax(up[v], up[u]);
checkMax(e[v], e[u] + 1);
int t = d[v][0] + 1;
if (d[u][0] == t) {
checkMax(up[v], d[u][1] + d[u][2]);
checkMax(up[v], d[u][1] + e[u]);
checkMax(e[v], d[u][1] + 1);
}
else {
if (d[u][1] == t) checkMax(up[v], d[u][0] + d[u][2]);
else checkMax(up[v], d[u][0] + d[u][1]);
checkMax(up[v], d[u][0] + e[u]);
checkMax(e[v], d[u][0] + 1);
}
dfs2(v, u);
}
if (K == 2) checkMax(z, dn[u] + up[u]);
upd(d[u], e[u]); checkMax(z, d[u][0] + d[u][1] + (K == 2 ? d[u][2] + d[u ][3] : 0));
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif
RD(n, K); DO(n-1) {
int x, y; RD(x, y);
adj[x].PB(y);
adj[y].PB(x);
}
dfs1(); dfs2();
cout << 2*(n-1) - z + K << endl;
}
This article is reproduced from: https://www.shuizilong.com/house/archives/luogu-p3629-apio2010-%E5%B7%A1%E9%80%BB/
This site is only for collection, and the copyright belongs to the original author.