银联高校极客挑战赛 初赛 第一场 B

自学图论的码队弟弟

试图写非递归求解，然后TLE了一下午==，全程找不到bug，换成递归，一发AC

判断环写得很丑==

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define P pair<int,int>

vector<P> G[];

bool vis[];

int n;

int fa[];

int x[];

bool s[];

bool fx[];

int in=-;

int T=;

int a;

bool dfs(int x)

{

    T++;

   // if(vis[x])return false;

    //if(++T>100000)puts(0);

    for(int i=; i<G[x].size(); i++)

    {

        a=G[x][i].first;

        //if(G[a].size()==1)continue;

        if((a!=fa[x])&&(!vis[a]))

        {

            fa[a]=x;

            vis[a]=;

            if(dfs(a))

            {

                return true;

            }

        }

        else if((a!=fa[x])&&vis[a])

        {

            fa[a]=x;

            in=a;

            return true;

        }

    }

    return false;

}

void solve(int k)

{

    fx[k]=;

    int n=G[k].size();

    for(int i=;i<n;i++){

        int a=G[k][i].first;

        int b=G[k][i].second;

        x[a]=b-x[k];

        if(!fx[a])

        solve(a);

    }

}

int main()

{

    scanf("%d",&n);

    int a,b,c;

    int R=;

    for(int i=; i<n; i++)

    {

        scanf("%d%d%d",&a,&b,&c);

        G[a].push_back(P(b,c));

        G[b].push_back(P(a,c));

        if(G[a].size()>G[R].size())R=a;

        if(G[b].size()>G[R].size())R=b;

    }

    vis[R]=;

    dfs(R);

    int t=in;

    int g=,dd=;

    int ans=;

    while((!dd)||t!=in)

    {

        dd=;

        for(int i=; i<G[t].size(); i++)

        {

            if(G[t][i].first==fa[t])

            {

                ans+=g*G[t][i].second;

                g*=-;

                t=fa[t];

                break;

            }

        }

    }

    x[in]=ans/;

    fx[in]=;

    solve(in);

    /*while(true)

    {

        /*if(T+10>=100000){

            puts(0);

        }

        bool wa=0;

        /*for(int i=1; i<=n; i++)

        {

            if(!fx[i])

            {

                wa=1;

                break;

            }

        }

        if(!wa)break;

        if(t==-1)

        {

            for(int i=1; i<=n; i++)

            {

                if(fx[i]&&!(s[i]))

                {

                    t=i;

                    break;

                }

            }

            if(t==-1)break;

        }

        k=t;

        t=-1;

        for(int i=0; i<G[k].size(); i++)

        {

            int l=G[k][i].first;

            int r=G[k][i].second;

            x[l]=r-x[k];

            fx[l]=1;

            if(!s[l]&&t==-1)t=l;

        }

        s[k]=1;

    }

    */

    for(int i=; i<=n; i++)

    {

        cout<<x[i]<<'\n';

    }

}