(C++)水平1167ツリーの直径

質問と回答

https://www.acmicpc.net/problem/1167
木.
ああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああそう受け入れましょう.
dfsで上記の論理を実現するのが答えです

コード#コード#

#include <iostream>
#include <string.h>
#include <vector>
using namespace std;

struct leaf{
    int node; int length;
    leaf(int x, int y): node(x), length(y) {};
};



bool isVisited[100005];

int N; int ans=0;

int farestLeaf=0;
int depth=0;
vector<leaf> leafs[100005];

void solve(int x, int cnt){

    bool flag =false;

    for(int i=0; i< (int) leafs[x].size(); i++){
        int next = leafs[x][i].node;
        if(isVisited[next]) continue;
        isVisited[x]= true;
        solve(next, cnt+leafs[x][i].length);
        flag=true;
    }

    if(!flag){
        if (depth<cnt) {
            depth=cnt;
            farestLeaf = x;
        }
    }
}



int main(){
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

     cin>>N;

    //먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다.
    int node, length, a;
    for(int i=1; i<=N; i++){
        cin>>a;
        while(1){
            cin>>node; if(node==-1) break;
            cin>>length;
            leafs[a].push_back({node, length});
        }
    }


    solve(1, 0);
    int tmp = farestLeaf;
    memset(isVisited, false, sizeof(isVisited));
    farestLeaf=0;
    depth=0;

    solve(tmp, 0);

    cout<<depth;

}