Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
51709 MattL 树上博弈 C++ 运行超时 0 1000 MS 3368 KB 1465 2022-07-13 13:24:46

Tests(0/20):


#include<bits/stdc++.h> using namespace std; const int N = 1e5+10; long long n,m,u,v,uu,vv,w,r,fa[N],val[N],dep[N],rmax,maxn,minn,cnt; long long dp(long long k) { if(k==1)return 0; if(dep[k])return dep[k]; return dep[k]=dp(fa[k])+1; } long long dfs(long long k,long long kk) { if(dep[k]==dep[kk])return k; minn=min(minn,val[k]); if(maxn<val[k])cnt=0; maxn=max(maxn,val[k]); if(maxn==val[k])cnt++; if(val[k]<r)rmax=max(rmax,val[k]); return dfs(fa[k],kk); } void fs(int k,int kk) { if(k==kk)return ; minn=min(minn,min(val[k],val[kk])); if(maxn<val[k]||maxn<val[kk])cnt=0; maxn=max(maxn,max(val[k],val[kk])); if(maxn==val[kk])cnt++; if(maxn==val[k])cnt++; if(val[k]<r)rmax=max(rmax,val[k]); if(val[kk]<r)rmax=max(rmax,val[kk]); dfs(fa[k],fa[kk]); } long long ans() { if(uu==vv)return 1; if(r>maxn)return (cnt&1)?r-maxn:r; // if(r==minn)return 0; if(r==maxn)return !cnt&1; if(r>minn&&r<maxn)return r-rmax; if(r<minn)return r; } int main() { // freopen("game.in","r",stdin); // freopen("game.out","w",stdout); cin>>n; for(int i=1;i<n;i++) { cin>>u>>v>>w; if(fa[u]||u==1)fa[v]=u,val[v]=w; else fa[u]=v,val[u]=w; } for(int i=1;i<=n;i++) if(!dep[i]) dp(i); cin>>m; while(m--) { cin>>u>>v>>r; uu=u,vv=v; cnt=rmax=0,maxn=LONG_LONG_MIN,minn=LONG_LONG_MAX; if(dep[u]>dep[v])u=dfs(u,v); else v=dfs(v,u); fs(u,v); cout<<ans()<<endl; } return 0; }


测评信息: