mpc我看过了,有两个大块错了,我给你整理一下
**1变量 "maxlen" 的赋值问题。在代码的开头定义了全局变量 "maxlen",然后在主函数的计算过程中又定义了一个同名的局部变量,并且将计算出的最大长度赋值给了局部变量,而没有更新全局变量。因此,在最后输出结果时,使用的是未被更新的全局变量 "maxlen",导致结果错误。解决方法是将 int maxlen = 0; 改为 maxlen = 0;,即更新全局变量的值。**
在 DFS2 函数中, s[u] 的累加操作存在问题。现在的累加方式是 s[u] += s[j];,实际上应该是将节点 j 的子树节点数累加到节点 u 上,而不是直接将 s[j] 累加到 s[u]。解决方法是修改为 s[u] += s[j] + 1;,表示将节点 j 的子树节点数加上节点 j 本身,再累加到节点 u 上。
我大概写了半个小时,c++基础不好,我也写不太出来,可能好几个错,反正思路是对的
```cpp
#include <iostream>
#include <cstring>
using namespace std;
const int N = 300010,M = 2 * N,MAX_LOG = 18;
int n,m;
int h[N],e[M],ne[M],tmpw[M],idx;
int f[N][MAX_LOG];
int dis[N];
int maxlen;
int dep[N];
int s[N],w[N];
int num,ans;
void add_edge (int a,int b,int c) {
e[idx] = b;
tmpw[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
struct tran {
int a,b,LCA,len;
}t[N];
void DFS1 (int u,int fa) {
for (int i = h[u];~i;i = ne[i]) {
int j = e[i];
if (j == fa) continue;
dep[j] = dep[u] + 1;
dis[j] = dis[u] + tmpw[i];
w[j] = tmpw[i];
DFS1 (j,u);
f[j][0] = u;
for (int k = 1;k < MAX_LOG;k++) f[j][k] = f[f[j][k - 1]][k - 1];
}
}
void DFS2 (int u,int fa) {
for (int i = h[u];~i;i = ne[i]) {
int j = e[i];
if (j == fa) continue;
DFS2 (j,u);
s[u] += s[j] + 1;
}
if (s[u] == num) ans = max (ans,w[u]);
}
int get_LCA (int a,int b) {
if (dep[a] < dep[b]) swap (a,b);
for (int i = MAX_LOG - 1;i >= 0;i--) {
if (dep[f[a][i]] >= dep[b]) a = f[a][i];
}
if (a == b) return a;
for (int i = MAX_LOG - 1;i >= 0;i--) {
if (f[a][i] != f[b][i]) a = f[a][i],b = f[b][i];
}
return f[a][0];
}
bool check (int x) {
memset (s,0,sizeof (s));
num = ans = 0;
for (int i = 1;i <= m;i++) {
if (t[i].len > x) {
s[t[i].a]++,s[t[i].b]++,s[t[i].LCA] -= 2;
num++;
}
}
DFS2 (1,-1);
return maxlen - ans <= x;
}
int main () {
memset (h,-1,sizeof (h));
cin >> n >> m;
for (int i = 1;i <= n - 1;i++) {
int a,b,c;
cin >> a >> b >> c;
add_edge (a,b,c),add_edge (b,a,c);
}
dep[1] = 1;
DFS1 (1,-1);
maxlen = 0;
for (int i = 1;i <= m;i++) {
cin >> t[i].a >> t[i].b;
t[i].LCA = get_LCA (t[i].a,t[i].b);
t[i].len = dis[t[i].a] + dis[t[i].b] - 2 * dis[t[i].LCA];
maxlen = max (maxlen,t[i].len);
}
int l = 0,r = maxlen;
while (l < r) {
int mid = l + r >> 1;
if (check (mid)) r = mid;
else l = mid + 1;
}
cout << l << endl;
return 0;
}
```
by zh_goldfish @ 2023-07-23 09:48:14
@[zh_goldfish](/user/973744) 有一部分是对的
感谢
by incra @ 2023-07-23 15:34:57
@[zh_goldfish](/user/973744) 你的代码错了(((
by incra @ 2023-07-23 17:52:14
@[incra](/user/463956) 我都说了不保证对
by zh_goldfish @ 2023-07-23 20:17:40