QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#865930 | #5148. Tree Distance | ASnown | RE | 0ms | 0kb | C++17 | 3.8kb | 2025-01-22 08:56:28 | 2025-01-22 08:56:29 |
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