牛客練習試合27 C.水図(dfs+思考)

タイトルリンク:https://www.nowcoder.com/acm/contest/188/C
最小生成木の問題のように見えますが、実際には思考問題+暴捜です.一つのノードからすべてのノードを遍歴しなければならないので、必ず1つのパスを2回歩かなければなりませんが、1つのパスを1回しか歩かないので、私たちは最も長いパスを見つけて彼を1回だけ歩かせるだけです.したがって、最後の結果は、すべてのエッジの重み値の和の2倍から最も長いパスを減算します.
ACコード:

#include 
#define maxn 50005
#define ll long long
using namespace std;
struct Node{
    int to;
    ll w;
    int next;
}Edge[maxn << 1];
int head[maxn << 1];
int n,s,num;
ll maxx;

void init(){
    memset(head,-1,sizeof(head));
    num = 0;
}

void add(int u,int v,ll w){
    Edge[num].to = v;
    Edge[num].w = w;
    Edge[num].next = head[u];
    head[u] = num++;
}

void dfs(int x,int xx,ll step){
    maxx = max(maxx, step);
    for(int i=head[x];i!=-1;i=Edge[i].next){
        if(Edge[i].to == xx)continue;
        dfs(Edge[i].to, x, step + Edge[i].w);
    }
}

int main()
{
    init();
    scanf("%d%d",&n,&s);
    ll sum = 0;
    for(int i=1;i