我使用了错误的树的直径求法成功AC,即树的直径为一条链时,比如:
10 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
错误答案为 19,正确答案为 10。
错误代码:
if (!flag) maxx[u] = maxc[u] = 0, maxxp[u] = maxcp[u] = u;
if (res < maxx[u] + maxc[u]) {
res = maxx[u] + maxc[u];
resxp = maxxp[u];
rescp = maxcp[u];
}
正确代码应为:
if (!flag) maxx[u] = 0, maxxp[u] = u;
if (!maxcp[u]) {
if (res < maxx[u]) {
res = maxx[u];
resxp = maxxp[u];
rescp = 1;
}
}
else if (res < maxx[u] + maxc[u]) {
res = maxx[u] + maxc[u];
resxp = maxxp[u];
rescp = maxcp[u];
}
即要判断一个断点是否存在。