test/aoj/0391.test.cpp

View this file on GitHub
Last update: 2020-11-02 16:40:04+09:00
Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0391

Depends on

Code

// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0391

#include <bits/stdc++.h>
using namespace std;

#define call_from_test
#include "../../tools/chminmax.cpp"
#include "../../tree/levelancestor.cpp"
#undef call_from_test

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);
  const char newl = '\n';

  int n,q;
  cin>>n>>q;
  using P = pair<int, int>;
  vector<vector<P> > G(n);
  LevelAncestor la(n);
  for(int i=1;i<n;i++){
    int u,v,w;
    cin>>u>>v>>w;
    u--;v--;
    la.add_edge(u,v);
    G[u].emplace_back(v,w);
    G[v].emplace_back(u,w);
  }
  la.build();

  vector<int> dep(n,0);
  {
    queue<P> q;
    q.emplace(0,-1);
    while(!q.empty()){
      int v,p;
      tie(v,p)=q.front();q.pop();
      for(auto e:G[v]){
        int u,c;
        tie(u,c)=e;
        if(u==p) continue;
        dep[u]=dep[v]+c;
        q.emplace(u,v);
      }
    }
  }

  auto dist=[&](int u,int v){return dep[u]+dep[v]-2*dep[la.lca(u,v)];};
  auto path=
    [&](int u,int v,int d){
      if(d==0) return u;
      int r=la.lca(u,v);
      int x=la.distance(u,r),y=la.distance(r,v);
      if(d<=x) return la.up(u,d);
      return la.up(v,(x+y)-d);
    };

  for(int i=0;i<q;i++){
    int a,b,c;
    cin>>a>>b>>c;
    a--;b--;c--;
    auto calc=
      [&](int v,int u=-1){
        return max({dist(a,v)*(a!=u),
                    dist(b,v)*(b!=u),
                    dist(c,v)*(c!=u)});
      };

    int p=la.lca(a,b),q=la.lca(b,c),r=la.lca(c,a);
    int v=la.dep[p]>la.dep[q]?p:(la.dep[q]>la.dep[r]?q:r);

    int ans=min({calc(a),calc(b),calc(c),calc(v)});
    for(int u:{a,b,c}){
      if(calc(v,u)>=ans) continue;
      int l=0,r=la.distance(u,v);
      while(l+1<r){
        int m=(l+r)>>1;
        int x=path(u,v,m);
        if(calc(x,u)<dist(x,u)) r=m;
        else l=m;
      }
      chmin(ans,calc(path(u,v,l)));
      chmin(ans,calc(path(u,v,r)));
    }
    cout<<ans<<newl;
  }
  return 0;
}

#line 1 "test/aoj/0391.test.cpp"
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0391

#include <bits/stdc++.h>
using namespace std;

#define call_from_test
#line 1 "tools/chminmax.cpp"

#line 3 "tools/chminmax.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif
#line 1 "tree/levelancestor.cpp"

#line 3 "tree/levelancestor.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
struct LevelAncestor{
  vector<vector<int> > G,par,lad;
  vector<int> dep,nxt,len,pth,ord,hs;
  LevelAncestor(int n):
    G(n),dep(n),nxt(n,-1),len(n),pth(n),ord(n),hs(n+1,0){
    int h=1;
    while((1<<h)<=n) h++;
    par.assign(h,vector<int>(n,-1));
    for(int i=2;i<=n;i++) hs[i]=hs[i>>1]+1;
  }

  void add_edge(int u,int v){
    G[u].emplace_back(v);
    G[v].emplace_back(u);
  }

  void dfs(int v,int p,int d,int f){
    if(nxt[v]<0){
      par[0][nxt[v]=v]=p;
      len[v]=dep[v]=d;
      for(int u:G[v]){
        if(u==p) continue;
        dfs(u,v,d+1,0);
        if(len[v]<len[u]) nxt[v]=u,len[v]=len[u];
      }
    }
    if(!f) return;
    pth[v]=lad.size();
    lad.emplace_back();
    for(int k=v;;k=nxt[k]){
      lad.back().emplace_back(k);
      pth[k]=pth[v];
      if(k==nxt[k]) break;
    }
    for(;;p=v,v=nxt[v]){
      for(int u:G[v])
        if(u!=p and u!=nxt[v]) dfs(u,v,d+1,1);
      if(v==nxt[v]) break;
    }
  }

  void build(int r=0){
    int n=G.size();
    dfs(r,-1,0,1);
    for(int k=0;k+1<(int)par.size();k++){
      for(int v=0;v<n;v++){
        if(par[k][v]<0) par[k+1][v]=-1;
        else par[k+1][v]=par[k][par[k][v]];
      }
    }
    for(int i=0;i<(int)lad.size();i++){
      int v=lad[i][0],p=par[0][v];
      if(~p){
        int k=pth[p],l=min(ord[p]+1,(int)lad[i].size());
        lad[i].resize(l+lad[i].size());
        for(int j=0,m=lad[i].size();j+l<m;j++)
          lad[i][m-(j+1)]=lad[i][m-(j+l+1)];
        for(int j=0;j<l;j++)
          lad[i][j]=lad[k][ord[p]-l+j+1];
      }
      for(int j=0;j<(int)lad[i].size();j++)
        if(pth[lad[i][j]]==i) ord[lad[i][j]]=j;
    }
  }

  int lca(int u,int v){
    int h=par.size();

    if(dep[u]>dep[v]) swap(u,v);
    for(int k=0;k<h;k++)
      if((dep[v]-dep[u])>>k&1)
        v=par[k][v];

    if(u==v) return u;
    for(int k=h-1;k>=0;k--){
      if(par[k][u]==par[k][v]) continue;
      u=par[k][u];
      v=par[k][v];
    }
    return par[0][u];
  }

  int distance(int u,int v){
    return dep[u]+dep[v]-dep[lca(u,v)]*2;
  }

  int up(int v,int d){
    if(d==0) return v;
    v=par[hs[d]][v];
    d-=1<<hs[d];
    return lad[pth[v]][ord[v]-d];
  }

  // from u to v
  int next(int u,int v){
    if(dep[u]>=dep[v]) return par[0][u];
    int l=up(v,dep[v]-dep[u]-1);
    return par[0][l]==u?l:par[0][u];
  }
};
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif
#line 9 "test/aoj/0391.test.cpp"
#undef call_from_test

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);
  const char newl = '\n';

  int n,q;
  cin>>n>>q;
  using P = pair<int, int>;
  vector<vector<P> > G(n);
  LevelAncestor la(n);
  for(int i=1;i<n;i++){
    int u,v,w;
    cin>>u>>v>>w;
    u--;v--;
    la.add_edge(u,v);
    G[u].emplace_back(v,w);
    G[v].emplace_back(u,w);
  }
  la.build();

  vector<int> dep(n,0);
  {
    queue<P> q;
    q.emplace(0,-1);
    while(!q.empty()){
      int v,p;
      tie(v,p)=q.front();q.pop();
      for(auto e:G[v]){
        int u,c;
        tie(u,c)=e;
        if(u==p) continue;
        dep[u]=dep[v]+c;
        q.emplace(u,v);
      }
    }
  }

  auto dist=[&](int u,int v){return dep[u]+dep[v]-2*dep[la.lca(u,v)];};
  auto path=
    [&](int u,int v,int d){
      if(d==0) return u;
      int r=la.lca(u,v);
      int x=la.distance(u,r),y=la.distance(r,v);
      if(d<=x) return la.up(u,d);
      return la.up(v,(x+y)-d);
    };

  for(int i=0;i<q;i++){
    int a,b,c;
    cin>>a>>b>>c;
    a--;b--;c--;
    auto calc=
      [&](int v,int u=-1){
        return max({dist(a,v)*(a!=u),
                    dist(b,v)*(b!=u),
                    dist(c,v)*(c!=u)});
      };

    int p=la.lca(a,b),q=la.lca(b,c),r=la.lca(c,a);
    int v=la.dep[p]>la.dep[q]?p:(la.dep[q]>la.dep[r]?q:r);

    int ans=min({calc(a),calc(b),calc(c),calc(v)});
    for(int u:{a,b,c}){
      if(calc(v,u)>=ans) continue;
      int l=0,r=la.distance(u,v);
      while(l+1<r){
        int m=(l+r)>>1;
        int x=path(u,v,m);
        if(calc(x,u)<dist(x,u)) r=m;
        else l=m;
      }
      chmin(ans,calc(path(u,v,l)));
      chmin(ans,calc(path(u,v,r)));
    }
    cout<<ans<<newl;
  }
  return 0;
}