HDU 3660 Alice and Bob's Trip

ツリーdp、この問題はG++を選択すると入力だけがタイムアウトします.C++1900 ms+で漂っていました..しかし入力最適化後はかなり速くなり、1100 ms程度です.dfsは階層的に最値を求めればいいので、差が少なくてもゲームでしょう.bobまで取るときはできるだけ大きな分岐(条件LとRの間を満たす場合)を選び、逆にaliceはできるだけ小さい分岐を選びます.そして一度dfsでよい,時間複雑度はO(n)である.
 

#include<algorithm>

#include<iostream>

#include<cstring>

#include<fstream>

#include<sstream>

#include<vector>

#include<string>

#include<cstdio>

#include<bitset>

#include<queue>

#include<stack>

#include<cmath>

#include<map>

#include<set>

#define FF(i, a, b) for(int i=a; i<b; i++)

#define FD(i, a, b) for(int i=a; i>=b; i--)

#define REP(i, n) for(int i=0; i<n; i++)

#define CLR(a, b) memset(a, b, sizeof(a))

#define debug puts("**debug**")

#define LL long long

#define PB push_back

#define MP make_pair

#define eps 1e-8

using namespace std;



const int N = 500005;

const int INF = 1e9 + 7;



bool read(int &x)

{

    char c;

    while(c=getchar())

    {

        if(c == EOF) return 0;

        if(c<='9'&&c>='0')break;

    }

    x=c-'0';

    while(c=getchar())

    {

        if(c == EOF) return 0;

        else  if(c>'9'||c<'0')break;

        else x=x*10+c-'0';

    }

    return 1;

}



struct Edge

{

    int u, v, c;

} E[N << 1];



int fir[N], next[N << 1], tot, l, r;



void Add_Edge(int u, int v, int c)

{

    E[tot].u = u, E[tot].v = v, E[tot].c = c;

    next[tot] = fir[u], fir[u] = tot ++;

}



int dfs(int u, int fa, int c, bool lvl)

{

    int v, ret = INF, tmp;

    if(lvl) ret = 0;

    for(int i = fir[u]; ~i; i= next[i])

    {

        v = E[i].v;

        if(v != fa)

        {

            tmp = dfs(v, u, c + E[i].c, !lvl) + E[i].c;

            if((tmp + c >= l) && (tmp + c <= r))

            {

                if(lvl) ret = max(ret, tmp);

                else ret = min(ret, tmp);

            }

        }

    }

    if(ret == INF) ret = 0;

    return ret;

}



int main()

{

    int n, u, v, c, ans;

    while(read(n))

    {

        read(l);read(r);

        CLR(fir, -1);

        tot = 0;

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

        {

            read(u);read(v);read(c);

            Add_Edge(u, v, c);

            Add_Edge(v, u, c);

        }

        ans = -1;

        for(int i = fir[0]; ~i; i = next[i])

        {

            v = E[i].v;

            int tmp = dfs(v, 0, E[i].c, 0) + E[i].c;

            if(tmp >= l && tmp <= r)

            {

                ans = max(ans, tmp);

            }

        }

        if(ans == -1) puts("Oh, my god!");

        else printf("%d
", ans);

    }

}