369C Valera and Elections

http://codeforces.com/problemset/problem/369/C
木の遍歴、dfs検索、ルートノードから各分岐の末尾を検索して、道路状況を記録して、修復が必要なものがあれば、分岐の末尾のノードを答えに入れます
10 w個のポイントは隣接テーブルで保存する

#include <iostream>

using namespace std ;

typedef struct L{

    int s,t ;

    int v ;

    int nxt ; 

}L ;

L e[200005] ;

int head[100005] ;

int cnt ;

void ins(int s,int t,int v)

{

    e[cnt].t=t ;

    e[cnt].v=(v==2) ;

    e[cnt].nxt=head[s] ;

    head[s]=cnt++ ;

}

int ct ;

int ans[100005] ;

int vis[200005] ;

int dfs(int s,int droad)

{

    int flag=0 ;

    for(int i=head[s] ;i!=-1 ;i=e[i].nxt)

    {

        if(!vis[i])

        {

            if(i&1)

                vis[i-1]=1 ;

            else

                vis[i+1]=1 ;

            flag=dfs(e[i].t,e[i].v) || flag ;

        }

    }

    if(droad && flag==0)

    {

        ans[ct++]=s ;

        return 1 ;

    }

    return flag ;

}

void solve()

{

    ct=0 ;

    dfs(1,0) ;

    printf("%d
",ct) ;

    for(int i=0 ;i<ct ;i++)

    {

        if(!i)

            printf("%d",ans[i]) ;

        else

            printf(" %d",ans[i]) ;

    }

    putchar('
') ;

}

int main()

{

    int n;

    while(~scanf("%d",&n))

    {

        memset(head,-1,sizeof(head)) ;

        memset(vis,0,sizeof(vis)) ;

        cnt=0 ;

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

        {

            int a,b,c ;

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

            ins(a,b,c) ;ins(b,a,c) ;

        }

        solve() ;

    }

    return 0 ;

}

View Code