QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#694781#5439. Meet in the MiddlehewanyingWA 0ms18056kbC++143.2kb2024-10-31 18:38:582024-10-31 18:39:04

Judging History

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

  • [2024-10-31 18:39:04]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:18056kb
  • [2024-10-31 18:38:58]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const int N=1e5+5,M=5e5+5;
int n,m;
ll ans[M];
struct Nod{int x,id;};
vector<Nod> Q[N];
struct Edge{int v;ll w;};

namespace Tr{
  vector<Edge> G[N];
  int dfn[N],idx=0,st[20][N];
  ll d[N];
  
  void add(int u,int v,int w){G[u].pb({v,w}),G[v].pb({u,w});}
  
  void dfs(int u,int fa){
    dfn[u]=++idx,st[0][idx]=fa;
    for(auto i:G[u]) if(i.v!=fa) d[i.v]=d[u]+i.w,dfs(i.v,u);
  }
  
  int Min(int u,int v){return dfn[u]<dfn[v]?u:v;}
  
  void init(){
    for(int i=1;i<=n;i++) dfn[i]=d[i]=0,G[i].clear();
    for(int i=1,u,v,w;i<n;i++) cin>>u>>v>>w,G[u].pb({v,w}),G[v].pb({u,w});
    idx=0;
    dfs(1,0);
    for(int i=1;i<=__lg(n)+1;i++)
      for(int j=1;j+(1<<i)-1<=n;j++)
        st[i][j]=Min(st[i-1][j],st[i-1][j+(1<<(i-1))]);
  }
  
  int LCA(int u,int v){
    if(u==v) return u;
    u=dfn[u],v=dfn[v];
    if(u>v) swap(u,v);
    int s=__lg(v-u);
    return Min(st[s][u+1],st[s][v-(1<<s)+1]);
  }
  
  ll dis(int u,int v){return d[u]+d[v]-2ll*d[LCA(u,v)];}
}

namespace SGT{
  vector<Edge> G[N];
  
  int dfn[N],idx=0,rev[N],ed[N];
  ll d[N];
    
  void dfs(int u,int fa){
    rev[dfn[u]=++idx]=u;
    for(auto i:G[u]) if(i.v!=fa) d[i.v]=d[u]+i.w,dfs(i.v,u);
    ed[u]=idx;
  }
  
  #define mid ((l+r)>>1)
  #define lc p<<1
  #define rc p<<1|1
  #define lson l,mid,lc
  #define rson mid+1,r,rc
  
  struct pnt{int x;ll dx;};
  
  ll dis(pnt a,pnt b){
    if(a.x==b.x) return max(a.dx,b.dx);
    return Tr::dis(a.x,b.x)+a.dx+b.dx;
  }
  
  struct sgt{
    pnt a,b;
  }tr[N<<2];
  
  ll tg[N<<2];
  
  sgt operator + (sgt x,sgt y){
    sgt z=dis(x.a,x.b)>dis(y.a,y.b)?x:y;  
    for(auto i:{x.a,x.b}) for(auto j:{y.a,y.b})
      if(dis(i,j)>dis(z.a,z.b)) z={i,j};
    return z;
  }
  
  void pu(int p){tr[p]=tr[lc]+tr[rc];}
  void pt(int p,ll v){tg[p]+=v,tr[p].a.dx+=v,tr[p].b.dx+=v;}
  void pd(int p){if(tg[p]!=0) pt(lc,tg[p]),pt(rc,tg[p]),tg[p]=0;}

  void upd(int l,int r,int p,int x,int y,ll v){
    if(x<=l&&y>=r) return pt(p,v);
    pd(p);
    if(x<=mid) upd(lson,x,y,v);
    if(y>mid) upd(rson,x,y,v);
    pu(p);
  }
  
  void build(int l,int r,int p){
    tg[p]=0;
    if(l==r) return tr[p].a=tr[p].b={rev[l],d[rev[l]]},void();
    build(lson),build(rson),pu(p);
  }
  
  void mof(int l,int r,ll v){
    upd(1,n,1,l,r,v);
    if(l>1) upd(1,n,1,1,l-1,-v);
    if(r<n) upd(1,n,1,r+1,n,-v);
  }
  
  void solve(int u,int fa){
    for(auto i:Q[u]) ans[i.id]=max(dis(tr[1].a,(pnt){i.x,0}),dis(tr[1].b,(pnt){i.x,0}));
    for(auto i:G[u]) if(i.v!=fa){
      mof(dfn[i.v],ed[i.v],-i.w);
      solve(i.v,u);
      mof(dfn[i.v],ed[i.v],i.w);
    }
  }
  
  void init(){
    for(int i=1;i<=n;i++) dfn[i]=rev[i]=d[i]=ed[i]=0,G[i].clear(),Q[i].clear();
    idx=0;
    for(int i=1,u,v,w;i<n;i++) cin>>u>>v>>w,G[u].pb({v,w}),G[v].pb({u,w});
    Tr::init(),dfs(1,0),build(1,n,1);
    
    cin>>m;
    for(int i=1,u,v;i<=m;i++) cin>>u>>v,Q[u].pb({v,i});
    solve(1,0);
    for(int i=1;i<=m;i++) cout<<ans[i]<<'\n';
  }
}

void SOLVE(){
  cin>>n;
  SGT::init();
}

int main(){
  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  SOLVE();
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 18056kb

input:

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

output:

12

result:

wrong answer 1st numbers differ - expected: '6', found: '12'