結果

問題 No.898 tri-βutree
ユーザー plin92793134plin92793134
提出日時 2019-12-18 23:25:39
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 408 ms / 4,000 ms
コード長 3,893 bytes
コンパイル時間 1,796 ms
コンパイル使用メモリ 146,652 KB
実行使用メモリ 16,616 KB
最終ジャッジ日時 2024-11-08 23:15:41
合計ジャッジ時間 9,697 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 81 ms
16,492 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 408 ms
16,484 KB
testcase_08 AC 378 ms
16,492 KB
testcase_09 AC 364 ms
16,488 KB
testcase_10 AC 386 ms
16,488 KB
testcase_11 AC 354 ms
16,488 KB
testcase_12 AC 373 ms
16,488 KB
testcase_13 AC 370 ms
16,484 KB
testcase_14 AC 388 ms
16,488 KB
testcase_15 AC 372 ms
16,492 KB
testcase_16 AC 362 ms
16,488 KB
testcase_17 AC 381 ms
16,484 KB
testcase_18 AC 376 ms
16,484 KB
testcase_19 AC 371 ms
16,612 KB
testcase_20 AC 396 ms
16,616 KB
testcase_21 AC 406 ms
16,488 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include <unordered_map>
#include <iomanip>
#include <functional>
#include <bitset>
#include <complex>
#include <stack>
#include <cstdint>



#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define rrep(i, n) for(ll i = (ll)(n-1); i >= 0; i--)
#define repi(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rrepi(i,a,b) for(ll i=(ll)(b);i>=(ll)(a);i--)

#define all(x) (x).begin(),(x).end()

template<class T>inline bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>inline bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

typedef long long ll;

using namespace std;
template<typename M,typename F>
struct lctree{
  struct node{
    node *pp,*lp,*rp;
    bool rev;
    int idx,sz;
    M key,sum;
    node(int idx,M key):pp(nullptr),lp(nullptr),rp(nullptr),rev(0),idx(idx),key(key),sum(key){}
    bool is_root(){
      return !pp||(pp->lp!=this&&pp->rp!=this);
    }
  };

  F f;
  M m1;
  lctree(F f,M m1):f(f),m1(m1){}

  inline void toggle(node *t){
    swap(t->lp,t->rp);
    t->rev^=1;
  }
  inline void push(node *t){
    if(t->rev){
      update(t);
      if(t->lp)toggle(t->lp);
      if(t->rp)toggle(t->rp);
      t->rev=0;
    }
  }
  inline void update(node *t){
    t->sum=t->key;
    t->sz=1;
    if(t->lp){t->sz+=t->lp->sz;t->sum=f(t->lp->sum,t->sum);}
    if(t->rp){t->sz+=t->rp->sz;t->sum=f(t->sum,t->rp->sum);}
  }
  inline void rotr(node *t) {
      auto *x = t->pp, *y = x->pp;
      if((x->lp = t->rp)) t->rp->pp = x;
      t->rp = x, x->pp = t;
      update(x), update(t);
      if((t->pp = y)) {
        if(y->lp == x) y->lp = t;
        if(y->rp == x) y->rp = t;
        update(y);
      }
    }
  inline void rotl(node *t) {
    auto *x = t->pp, *y = x->pp;
    if((x->rp = t->lp)) t->lp->pp = x;
    t->lp = x, x->pp = t;
    update(x), update(t);
    if((t->pp = y)) {
      if(y->lp == x) y->lp = t;
      if(y->rp == x) y->rp = t;
      update(y);
    }
  }
  inline void splay(node *t) {
    push(t);
    while(!t->is_root()) {
      auto *q = t->pp;
      if(q->is_root()) {
        push(q), push(t);
        if(q->lp == t) rotr(t);
        else rotl(t);
      } else {
        auto *r = q->pp;
        push(r), push(q), push(t);
        if(r->lp == q) {
          if(q->lp == t) rotr(q), rotr(t);
          else rotl(t), rotr(t);
        } else {
          if(q->rp == t) rotl(q), rotl(t);
          else rotr(t), rotl(t);
        }
      }
    }
  }
  inline node *expose(node *x){
    node *rp=nullptr;
    for(node *p=x;p;p=p->pp){
      splay(p);
      p->rp=rp;
      update(p);
      rp=p;
    }
    splay(x);
    return rp;
  }
  void cut(node *c){
    expose(c);
    node *p=c->lp;
    c->lp=nullptr;
    p->pp=nullptr;
    update(p);
  }
  void link(node *c,node *p){
    evert(c);
    expose(c);
    expose(p);
    c->pp=p;
    p->rp=c;
    update(p);
  }
  void evert(node *p){
    expose(p);
    toggle(p);
    push(p);
  }
  node *lca(node *u,node *v){
    expose(u);
    return expose(v);
  }
  node *make_node(int idx,M val){
    return new node(idx,val);
  }
  M query(node *u,node *v){
    evert(u);
    expose(v);
    return v->sum;
  }
};






int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  auto f=[](ll a,ll b){return a+b;};
  lctree<ll,decltype(f)>lct(f,0LL);
  ll n;cin>>n;
  ll id=n;
  vector<decltype(lct.make_node(0,0))> no;
  rep(i,n){
    no.push_back(lct.make_node(i,0));
  }
  rep(i,n-1){
    ll a,b,c;cin>>a>>b>>c;
    auto tn=lct.make_node(id++,c);
    lct.link(tn,no[a]);
    lct.link(no[b],tn);
  }
  ll q;cin>>q;
  rep(i,q){
    ll a,b,c;cin>>a>>b>>c;
    cout<<(lct.query(no[a],no[b])+lct.query(no[b],no[c])+lct.query(no[c],no[a]))/2<<"\n";
  }
  cout<<flush;


  return 0;

}
0