提出 #41148690

---

ソースコード 拡げる

#include <atcoder/all>
using namespace atcoder;
#include <bits/stdc++.h>
#include <cassert>
using namespace std;
using ll = long long;
const double pi = 3.14159265359;
const ll INF = 1LL << 60;

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

//using mint = modint998244353;
//using mint = modint1000000007;
//using mint = modint;  // mint::set_mod(p); later
//using mint = static_modint<1000000009>;

int N;
vector<int> u, v, w;
vector<vector<pair<int, int>>> edges;

// vs: DFS で巡った頂点の列
// es: vs に対応する辺の番号
// idx: 各頂点が vs に最初に現れるインデックス
// depth: 深さ
vector<int> vs, es, idx, depth;

void dfs(int v, int par, int e, int d)
{
  idx[v] = (int) vs.size();
  vs.push_back(v);
  depth.push_back(d);

  for (auto p : edges[v]){
    auto [nv, ne] = p;
    if (nv != par){
      es.push_back(ne);
      dfs(nv, v, ne, d+1);
      vs.push_back(v);
      depth.push_back(d);
    }
  }

  es.push_back(-e); // 帰りの辺番号
}

ll op(ll a, ll b){ return a + b; }
ll e(){ return 0; }

pair<int, int> op2(pair<int, int> a, pair<int, int> b){ return min(a, b); }
pair<int, int> e2(){ return make_pair((int) 1e9, -1); }

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

  // 1. Input
  cin >> N;
  u.resize(N-1);
  v.resize(N-1);
  w.resize(N-1);
  edges.resize(N);
  for (int i = 0; i < N - 1; i++){
    cin >> u[i] >> v[i] >> w[i];
    u[i]--;
    v[i]--;
    edges[u[i]].emplace_back(v[i], i+1);
    edges[v[i]].emplace_back(u[i], i+1);
  }

  // 2. DFS： オイラーツアー
  idx.resize(N);
  if (N > 1)
    dfs(0, -1, -1, 0);

  // 3. 経路の距離を管理
  segtree<ll, op, e> seg((int) es.size());
  vector<vector<int>> vp(N-1), vn(N-1);
  for (int i = 0; i < (int) es.size(); i++){
    int j = es[i];
    if (j > 0){
      j--;
      seg.set(i, w[j]);
      vp[j].push_back(i);
    } else {
      j = -j;
      j--;
      seg.set(i, -w[j]);
      vn[j].push_back(i);
    }
  }

  // 4. LCA のための seg
  segtree<pair<int, int>, op2, e2> rmq((int) depth.size());
  for (int i = 0; i < (int) depth.size(); i++){
    rmq.set(i, make_pair(depth[i], i));
  }
  
  // Query
  int Q;
  cin >> Q;
  for (int i = 0; i < Q; i++){
    int ty;
    cin >> ty;
    if (ty == 1){
      int i, w;
      cin >> i >> w;
      i--;
      for (int j : vp[i]){
	seg.set(j, w);
      }
      for (int j : vn[i]){
	seg.set(j, -w);
      }
    } else {
      int u, v;
      cin >> u >> v;
      u--; v--;

      if (u == v){
	cout << "0\n";
      } else {
	int l = idx[u];
	int r = idx[v];
	if (l > r) swap(l, r);

	auto [d, j] = rmq.prod(l, r+1);
	int lca = idx[vs[j]];

	ll dist = seg.prod(min(lca, l), max(lca, l)) + seg.prod(min(lca, r), max(lca, r));
	cout << dist << "\n";
      }
    }
  }
  
  return 0;
}

提出情報

ジャッジ結果