HDU-3660 Alice and Bob's Trip 树形dp

题意：有一棵树，Alice和Bob两个人要从树根走到叶子。Alice想要路径尽量短，Bob想要路径尽量长，且路径长度一定要在[L,R]区间范围内。从根节点开始Bob和Alice轮流选择走那条路，问Bob能选到的最长路径是什么？

解法：这道题一看到就想Bob从儿子中选最长的，Alice从儿子中选最短的就可以了，码了之后就过了。。。但是之后想想觉得有点不对劲，因为Bob想要尽量长，要是他这回合选了最长的儿子，那么下一回合就是Alice选了，那么Alice会不会选一条对Bob不利的路，使得其实Bob在上一回合选一条次长的而不是最长的反而会更划算。（如果按照这个思路想的话，那Bob就应该从儿子中选一个最短的最长来避免最保证最坏情况的发生）。关于这个疑问蒟蒻博主还现在没想明白。

另外，这道题对时间要求极高，博主需要用到输入挂才顺利通过。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int N=5e5+10;
const int INF=0x3f3f3f3f;
int n,l,r,indeg[N];

//inline int read() {
//    int x=0, f=1; register char ch=getchar();
//    for (; ch<'0' || ch>'9'; ch=getchar()) if (ch=='-') f=-1;
//    for (; ch>='0' && ch<='9'; ch=getchar()) x=x*10+ch-'0';
//    return x*f;
//}
#define reg register
#define fok (ch!=EOF)
#define sep (ch==' '||ch=='
'||ch=='	')
#define dsep !isdigit(ch)
#define neq(a,b) ((a)-(b)>1e-6)
struct FastIO{
    char rbuf[1000002],wbuf[1000002],b,*p1,*p2;
    int rs,ws,S;
    FastIO(){p1=rbuf,p2=wbuf,S=1000000,rs=1000000,ws=-1,b=1;}
    inline void go(){fwrite(wbuf,1,ws+1,stdout)?ws=-1:0;}
    inline char getch(){
        return rs==S&&
        (p1=rbuf,rs=-1,(S=fread(rbuf,1,S+1,stdin)-1)==-1)?
        (b=0,EOF):(++rs,*p1++);
    }
    inline void putch(int x){
        ws==1000000&&
        (p2=wbuf,ws=-1,fwrite(wbuf,1,1000001,stdout)),++ws,*p2++=x;
    }
    inline void puts(char str[]){
        for(reg int i=0;str[i]!='

HDU-3660 Alice and Bob's Trip 树形dp

相关推荐