QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#865930#5148. Tree DistanceASnownRE 0ms0kbC++173.8kb2025-01-22 08:56:282025-01-22 08:56:29

Judging History

你现在查看的是最新测评结果

  • [2025-01-22 08:56:29]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2025-01-22 08:56:28]
  • 提交

answer

#include<bits/stdc++.h>
#define file(F) freopen(#F".in","r",stdin),freopen(#F".out","w",stdout)
#define lowbit(x) ((x)&-(x))
#define ALL(x) (x).begin(),(x).end()
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define popc(x) (__builtin_popcountll((x)))
#define abs(x) ((x)>=0?(x):-(x))
using namespace std;
using ll=long long;
using uint=uint32_t;
namespace asnown {
using i32=int32_t; using u32=uint32_t;
using i64=int64_t; using u64=uint64_t;
using i128=__int128_t; using u128=__uint128_t; };
template<typename T>
inline bool Max(T &x,T y) { return std::less<T>()(x,y)&&(x=y,true); }
template<typename T>
inline bool Min(T &x,T y) { return std::less<T>()(y,x)&&(x=y,true); }
void Solve();
const int N = 2e5+25;
int n,Q;
vector<pair<int,int>> e[N];
vector<pair<int,int>> up;
vector<pair<int,int>> qry[N]; ll ans[N];
vector<int> upd[N];
ll dep[N];
int dfn[N],dfx;
int st[N][20];
void dfs(int u,int fa) {
   dfn[u]=++dfx;
   st[dfn[u]][0]=fa;
   for(auto [v,w]:e[u]) if(v!=fa)
      dep[v]=dep[u]+w,dfs(v,u);
}
int LCA(int x,int y) {
   if(x==y) return x;
   if((x=dfn[x])>(y=dfn[y])) swap(x,y);
   int l=__lg(y-x++);
   return min(st[x][l],st[y-(1<<l)+1][l],
    [&](int x,int y){ return dfn[x]<dfn[y]; });
} inline ll dis(int x,int y) { return dep[x]+dep[y]-2*dep[LCA(x,y)]; }
int sz[N],mx[N],cent;
bool vis[N];
void Findcent(int u,int fa,int sum) {
   sz[u]=1,mx[u]=0;
   for(auto [v,w]:e[u]) if(v!=fa&&!vis[v]) {
      Findcent(v,u,sum); sz[u]+=sz[v];
      Max(mx[u],sz[v]);
   }
   Max(mx[u],sum-sz[u]);
   if(mx[u]<mx[cent]) cent=u;
}
void solve(int rt,int sum) {
   vis[rt]=true;
   vector<int> p;
   static ll d[N];
   auto dfs=[&](auto &self,int u,int fa)->void {
      p.emplace_back(u); d[u]=dis(u,rt);
      for(auto [v,w]:e[u]) if(v!=fa&&!vis[v])
         self(self,v,u);
   }; dfs(dfs,rt,0);
   sort(ALL(p),[&](int x,int y){ return d[x]<d[y]; });
   set<int> s;
   for(auto i:p) {
      auto x=s.insert(i).first;
      if(x!=s.begin()) up.emplace_back(*prev(x),*x);
      if(++x!=s.end()) up.emplace_back(*prev(x),*x);
   }
   for(auto [v,w]:e[rt]) if(!vis[v]) {
      int szv=sz[rt]>sz[v]?sz[v]:sum-sz[rt];
      cent=0,Findcent(v,rt,szv);
      solve(v,szv);
   }
}
namespace SGT {
const int N = ::N<<2;
#define mid ((L+R)>>1)
#define ls (u<<1)
#define rs (ls|1)
ll mn[N];
void build(int u,int L,int R) {
   mn[u]=0x3f3f3f3f3f3f3f3f;
   if(L==R) return ;
   build(ls,L,mid),build(rs,mid+1,R);
}
void update(int u,int L,int R,int x,ll k) {
   Min(mn[u],k); if(L==R) return ;
   if(x<=mid) update(ls,L,mid,x,k);
   else update(rs,mid+1,R,x,k);
}
ll query(int u,int L,int R,int l,int r) {
   if(l<=L&&R<=r) return mn[u];
   if(r<=mid) return query(ls,L,mid,l,r);
   if(l> mid) return query(rs,mid+1,R,l,r);
   return min(query(ls,L,mid,l,r),query(rs,mid+1,R,l,r));
}
#undef mid
#undef ls
#undef rs
}
signed main() {
#ifndef ONLINE_JUDGE
#endif
   cin.tie(nullptr)->sync_with_stdio(false);
   Solve();
}
void Solve() {
   cin>>n;
   for(int i=1;i<n;i++) {
      int u,v,w; cin>>u>>v>>w;
      e[u].emplace_back(v,w);
      e[v].emplace_back(u,w);
   }
   dfs(1,0);
   for(int l=0;l<19;l++) for(int i=1;i+(1<<l+1)-1<=n;i++)
      st[i][l+1]=min(st[i][l],st[i+(1<<l)][l],
       [&](int x,int y){ return dfn[x]<dfn[y]; });
   mx[cent=0]=n,Findcent(1,0,n);
   solve(cent,n);
   assert(false);
   for(auto [l,r]:up) upd[r].emplace_back(l);
   cin>>Q;
   for(int i=1;i<=Q;i++) {
      int l,r; cin>>l>>r;
      qry[r].emplace_back(l,i);
   }
   SGT::build(1,1,n);
   for(int i=1;i<=n;i++) {
      for(auto x:upd[i]) SGT::update(1,1,n,x,dis(x,i));
      for(auto [l,id]:qry[i]) {
         ans[id]=SGT::query(1,1,n,l,i);
         if(ans[id]==0x3f3f3f3f3f3f3f3f) ans[id]=-1;
      }
   }
   for(int i=1;i<=Q;i++) printf("%lld\n",ans[i]);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Runtime Error

input:

5
1 2 5
1 3 3
1 4 4
3 5 2
5
1 1
1 4
2 4
3 4
2 5

output:


result: