题意：有一棵树，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]!=' ';)putch(str[i]),++i; } inline void getline(string& s){ for(reg char ch;(ch=getch())!=' '&&fok;)s+=ch; } inline FastIO& operator>>(int& x){ x=0;reg char f=0,ch=getch(); while(dsep&&fok)f|=(ch=='-'),ch=getch(); while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getch(); return x=f?-x:x,*this; } inline FastIO& operator>>(long long& x){ x=0;reg char f=0,ch=getch(); while(dsep&&fok)f|=(ch=='-'),ch=getch(); while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getch(); return x=f?-x:x,*this; } inline FastIO& operator>>(char& ch){return ch=getch(),*this;} inline FastIO& operator>>(string& s){ reg char ch=getch(); while(sep&&fok)ch=getch(); while(!sep&&fok)s+=ch,ch=getch(); return *this; } inline FastIO& operator>>(double& x){ x=0;reg char f=0,ch=getch(); double d=0.1; while(dsep&&fok)f|=(ch=='-'),ch=getch(); while(isdigit(ch))x=x*10+(ch^48),ch=getch(); if(ch=='.') while(isdigit(ch=getch()))x+=d*(ch^48),d*=0.1; return x=f?-x:x,*this; } inline FastIO& operator<<(int x){ reg char ch[10],i=-1; !x?(putch('0'),0):0, x<0?(putch('-'),x=-x):0; while(x)ch[++i]=x%10+48,x/=10; while(~i)putch(ch[i]),--i; return *this; } inline FastIO& operator<<(long long x){ reg char ch[20],i=-1; !x?(putch('0'),0):0, x<0?(putch('-'),x=-x):0; while(x)ch[++i]=x%10+48,x/=10; while(~i)putch(ch[i]),--i; return *this; } inline FastIO& operator<<(char ch){return putch(ch),*this;} inline FastIO& operator<<(char str[]){return puts(str),*this;} inline FastIO& operator<<(string s){ reg int nn=s.size(); for(reg int i=0;i<nn;++i)putch(s[i]); return *this; } inline FastIO& operator<<(double x){ int y=int(x); *this<<y; x-=y; while(neq(x,int(x)))x*=10; x?*this<<'.'<<int(x):0; return *this; } inline operator bool(){return b;} }; FastIO io; //输入挂 int cnt=1,head[N],nxt[N<<1],to[N<<1],Len[N<<1]; void add_edge(int x,int y,int z) { nxt[++cnt]=head[x]; to[cnt]=y; Len[cnt]=z; head[x]=cnt; } int dp[N]; void dfs(int x,int dep,int len,int fa) { if (indeg[x]==1 && x!=1) { //Leaf if (l<=len && len<=r) dp[x]=0; else dp[x]=-1; return; } if (dep%2==1) dp[x]=0; else dp[x]=INF; for (int i=head[x];i;i=nxt[i]) { int y=to[i]; if (y==fa) continue; dfs(y,dep+1,len+Len[i],x); if (dp[y]==-1) continue; if (dep%2==1) { //Bob dp[x]=max(dp[x],dp[y]+Len[i]); } else { //Alice dp[x]=min(dp[x],dp[y]+Len[i]); } } if (dp[x]==0 || dp[x]==INF) dp[x]=-1; } int main() { while (io>>n) { io>>l>>r; cnt=1; for (int i=1;i<=n;i++) head[i]=0,indeg[i]=0; for (int i=1;i<n;i++) { int x,y,z; io>>x>>y>>z; x++; y++; indeg[x]++; indeg[y]++; add_edge(x,y,z); add_edge(y,x,z); } dfs(1,1,0,0); if (dp[1]==-1) puts("Oh, my god!"); else printf("%d ",dp[1]); } return 0; }