結果

問題 No.898 tri-βutree
コンテスト
ユーザー niuez
提出日時 2020-02-05 19:57:09
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 170 ms / 4,000 ms
コード長 3,992 bytes
コンパイル時間 1,044 ms
コンパイル使用メモリ 81,380 KB
実行使用メモリ 35,468 KB
最終ジャッジ日時 2024-11-08 23:23:05
合計ジャッジ時間 5,809 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <vector>
#include <iostream>
#include <set>
using namespace std;

namespace niu {

  const int N_MAX = 1e5 + 1;
  int par[N_MAX];
  int rank[N_MAX];

  struct union_find {
    union_find(int n) {
      for(int i = 0;i < n;i++) par[i] = i;
    }
    int root(int i) {
      return par[i] == i ? i : par[i] = root(par[i]);
    }
    /* unite x, y return parent */
    int unite(int x,int y) {
      x = root(x);
      y = root(y);
      if(x == y) return -1;
      if(rank[x] < rank[y]) {
        par[x] = y;
        return y;
      }
      else {
        par[y] = x;
        if(rank[x] == rank[y]) rank[x]++;
        return x;
      }
    }
  };

  using i64 = long long;

  using E = pair<int, i64>;
  vector<E> G[N_MAX];
  int ance[N_MAX];
  i64 weight[N_MAX];
  int qi = 0;
  vector<pair<int, int>> q[N_MAX];
  int ans[N_MAX * 3];
  int query[N_MAX][3];
  struct tarjans_offline_lca {
    union_find uf;
    tarjans_offline_lca(int n): uf(n) {}

    void add_edge(int a, int b, i64 w) {
      G[a].push_back({ b, w });
      G[b].push_back({ a, w });
    }
    void add_query(int a, int b) {
      q[a].push_back({ b, qi });
      q[b].push_back({ a, qi });
      qi++;
    }
    void dfs(int v, int f, i64 W) {
      ance[v] = v;
      weight[v] = W;
      for(auto e: G[v]) {
        int u = e.first;
        i64 w = e.second;
        if(f == u) continue;
        dfs(u, v, w + W);
        uf.unite(u, v);
        ance[uf.root(v)] = v;
      }
      for(auto e: q[v]) {
        int u = e.first;
        int i = e.second;
        if(ans[i] == -1) ans[i] = -2;
        else if(ans[i] == -2) ans[i] = ance[uf.root(u)];
      }
    }
    void offline_lca(int root) {
      for(int i = 0; i < N_MAX * 3; i++) ans[i] = -1;
      dfs(root, -1, 0);
    }
  };
}

#include <cstdio>

namespace niu {
  char cur;
  struct FIN {
    static inline bool is_blank(char c) { return c <= ' '; }
    inline char next() { return cur = getc_unlocked(stdin); }
    inline char peek() { return cur; }
    inline void skip() { while(is_blank(next())){} }
#define intin(inttype)  \
    FIN& operator>>(inttype& n) { \
      bool sign = 0; \
      n = 0; \
      skip(); \
      while(!is_blank(peek())) { \
        if(peek() == '-') sign = 1; \
        else n = (n << 1) + (n << 3) + (peek() & 0b1111); \
        next(); \
      } \
      if(sign) n = -n; \
      return *this; \
    }
    intin(int)
      intin(long long)
  } fin;

  char tmp[128];
  struct FOUT {
    static inline bool is_blank(char c) { return c <= ' '; }
    inline void push(char c) { putc_unlocked(c, stdout); }
    FOUT& operator<<(char c) { push(c); return *this; }
    FOUT& operator<<(const char* s) { while(*s) push(*s++); return *this; }
#define intout(inttype) \
    FOUT& operator<<(inttype n) { \
      if(n) { \
        char* p = tmp + 127; bool neg = 0; \
        if(n < 0) neg = 1, n = -n; \
        while(n) *--p = (n % 10) | 0b00110000, n /= 10; \
        if(neg) *--p = '-'; \
        return (*this) << p; \
      } \
      else { \
        push('0'); \
        return *this; \
      } \
    }
    intout(int)
      intout(long long)
  } fout;
}
#include <iostream>

int main() {
  using niu::fin;
  using niu::fout;
  using i64 = long long;
  i64 N;
  fin >> N;

  niu::tarjans_offline_lca eul(N);
  for(int i = 0;i < N - 1;i++) {
    i64 a, b, c;
    niu::fin >> a >> b >> c;
    eul.add_edge(a, b, c);
  }

  i64 Q;
  fin >> Q;
  for(i64 q = 0; q < Q; q++) {
    i64 x, y, z;
    fin >> x >> y >> z;
    eul.add_query(x, y);
    eul.add_query(y, z);
    eul.add_query(x, z);
    niu::query[q][0] = x;
    niu::query[q][1] = y;
    niu::query[q][2] = z;
  }
  eul.offline_lca(0);

  auto dist = [&](i64 i, i64 j) -> i64 {
    int a = niu::query[i][j];
    int b = niu::query[i][(j + 1) == 3 ? 0 : (j + 1)];
    int c = niu::ans[i * 3 + j];
    return niu::weight[a] + niu::weight[b] - 2 * niu::weight[c];
  };
  for(i64 q = 0; q < Q; q++) {
    fout << (dist(q, 0) + dist(q, 1) + dist(q, 2)) / 2 << "\n";
  }
}
0