在C++中使用双DFS寻找树的直径

Question

我正在尝试在SPOJ上解决一个问题，我应该找到一棵树上任意两个节点之间的最长路径。输入的内容包括testcases的数量t，节点的数量n，后面是由 "a b l "给出的n-1条边，a指节点1，b指节点2，l指边的长度。我尝试使用双df法，先对节点1执行dfs，以找到从节点1开始的最长路径。之后，我在离节点1最远的节点上执行dfs，找到可能的最长距离。不幸的是，我的代码是错误的，我完全不知道为什么，我希望有人能帮助我。先谢谢你了

EDIT：忘记说了，我确实用双BFS解决了这个问题。我想尝试使用DFS也解决这个问题，因为DFS据说比BFS更容易实现，但使用DFS给了我错误的答案。

#include <bits/stdc++.h>

using namespace std;

vector<pair<int, int>> adj[50001];
bool visited[50001] = {0};
int maxdist = -1, maxnode = -1;

void dfs(int node, int d)
{
    visited[node] = 1;
    if (d > maxdist)
    {
        maxdist = d;
        maxnode = node;
    }
    for(auto u: adj[node])
    {
        if(!visited[u.first])
        {
            dfs(u.first, d+u.second);
        }

    }
    return;
}

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        for (int i = 0; i < n-1; i++)
        {
            int a, b, l;
            cin >> a >> b >> l;
            adj[a].push_back(make_pair(b, l));
            adj[b].push_back(make_pair(a, l));
        }

        dfs(1, 0);
        for(int i = 1; i <= n; i++)
        {
            visited[i] = 0;
        }
        dfs(maxnode, 0);

        cout << maxdist << endl;

    }

}

Answer 1

不知道这样做是否能行得通，但是你在不同的测试用例之间共享了 adj[]和 visited[]，一定要在新的测试用例之前把它们清理掉。