結果

問題 No.1641 Tree Xor Query
ユーザー 👑 NachiaNachia
提出日時 2021-08-06 21:24:41
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 107 ms / 5,000 ms
コード長 3,609 bytes
コンパイル時間 1,117 ms
コンパイル使用メモリ 90,636 KB
実行使用メモリ 14,308 KB
最終ジャッジ日時 2023-10-17 02:43:12
合計ジャッジ時間 2,477 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 AC 2 ms
4,348 KB
testcase_03 AC 2 ms
4,348 KB
testcase_04 AC 2 ms
4,348 KB
testcase_05 AC 2 ms
4,348 KB
testcase_06 AC 2 ms
4,348 KB
testcase_07 AC 2 ms
4,348 KB
testcase_08 AC 2 ms
4,348 KB
testcase_09 AC 2 ms
4,348 KB
testcase_10 AC 2 ms
4,348 KB
testcase_11 AC 2 ms
4,348 KB
testcase_12 AC 2 ms
4,348 KB
testcase_13 AC 107 ms
13,916 KB
testcase_14 AC 106 ms
13,916 KB
testcase_15 AC 4 ms
4,348 KB
testcase_16 AC 9 ms
4,564 KB
testcase_17 AC 6 ms
4,348 KB
testcase_18 AC 7 ms
4,348 KB
testcase_19 AC 5 ms
4,348 KB
testcase_20 AC 79 ms
14,308 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define rep(i,n) for(int i=0; i<(n); i++)


struct HLD{

  int N;
  vector<int> P;
  vector<int> PP;
  vector<int> PD;
  vector<int> D;

  vector<int> rangeL;
  vector<int> rangeR;

  HLD(const vector<vector<int>>& E = {}){
    N = E.size();
    P.assign(N, -1);
    vector<int> I = {0};
    rep(i,I.size()){
      int p = I[i];
      for(int e : E[p]) if(P[p] != e){
        I.push_back(e);
        P[e] = p;
      }
    }
    vector<int> Z(N, 1);
    for(int i=N-1; i>=1; i--) Z[P[I[i]]] += Z[I[i]];
    PP.resize(N);
    for(int i=0; i<N; i++) PP[i] = i;
    vector<int> nx(N, -1);
    for(int p : I) if(p != 0){
      if(nx[P[p]] == -1) nx[P[p]] = p;
      if(Z[nx[P[p]]] < Z[p]) nx[P[p]] = p;
    }
    rep(i,N) if(nx[i] != -1) PP[nx[i]] = i;
    for(int p : I) if(p != 0) PP[p] = PP[PP[p]];

    PD.assign(N,N);
    PD[0] = 0;
    for(int p : I) if(p != 0) PD[p] = min(PD[PP[p]], PD[P[p]]+1);
    D.assign(N,0);
    for(int p : I) D[p] = ((PP[p] == p) ? 0 : D[P[p]]+1);
    
    rangeL.assign(N,-1);
    rangeR.assign(N,-1);
    vector<int> dfs;
    int ir = 0;
    dfs.push_back(0);
    while(dfs.size()){
      int p = dfs.back();
      dfs.pop_back();
      if(p < 0){ rangeR[-1-p] = ir; continue; }
      dfs.push_back(-1-p);
      for(int e : E[p]) if(P[p] != e) if(e != nx[p]) dfs.push_back(e);
      if(nx[p] != -1) dfs.push_back(nx[p]);
      rangeL[p] = ir++;
    }
  }

  int lca(int u, int v){
    if(PD[u] < PD[v]) swap(u, v);
    while(PD[u] > PD[v]) u = P[PP[u]];
    while(PP[u] != PP[v]){ u = P[PP[u]]; v = P[PP[v]]; }
    return (D[u] > D[v]) ? v : u;
  }

  vector<pair<int,int>> getpath(int r, int c){
    vector<pair<int,int>> res;
    while(PD[r] < PD[c]){
      res.push_back({ rangeL[PP[c]], rangeL[c]+1 });
      c = P[PP[c]];
    }
    if(PP[r] != PP[c]) return {};
    if(D[r] > D[c]) return {};
    res.push_back({ rangeL[r], rangeL[c]+1 });
    reverse(res.begin(), res.end());
    return move(res);
  }
};


struct RQ {
  using S = ll;
  static S op(S l, S r){ return { l ^ r }; }
  static S e(){ return { 0 }; }

  int N;
  vector<S> A;

  void mergev(int i){
    if(i<N) A[i] = op(A[i*2], A[i*2+1]);
  }
  
  RQ(int n){
    N=1; while (N<n) N*=2;
    A.assign(N*2,e());
  }
  RQ(const vector<S>& a) : RQ(a.size()){
    for(int i=0; i<a.size(); i++) A[i+N] = a[i];
    for(int i=N-1; i>=1; i--) mergev(i);
  }

  void set(int p, S x){
    p+=N; A[p] = x;
    for(int d=1; (1<<d)<=N; d++) mergev(p>>d);
  }
  S get(int p){
    return A[N+p];
  }

  S prod(int l, int r, int a=0, int b=0, int i=-1){
    if(i==-1){ a=0; b=N; i=1; }
    if(r<=a || b<=l) return e();
    if(l<=a && b<=r) return A[i];
    S q1 = prod(l, r, a, (a+b)/2, i*2);
    S q2 = prod(l, r, (a+b)/2, b, i*2+1);
    return op(q1, q2);
  }

};


int main() {
  int N,Q; cin >> N >> Q;
  vector<ll> A(N);
  rep(i,N) cin >> A[i];
  vector<vector<int>> E(N);
  rep(i,N-1){
    int u,v; cin >> u >> v; u--; v--;
    E[u].push_back(v);
    E[v].push_back(u);
  }
  HLD hld(E);
  RQ rq(N);
  rep(i,N) rq.set(hld.rangeL[i], A[i]);

  rep(q,Q){
    int t; cin >> t;
    if(t == 1){
      int p,x; cin >> p >> x; p--;
      int rp = hld.rangeL[p];
      rq.set(rp, rq.get(rp) ^ x);
    }
    if(t == 2){
      int u, x; cin >> u >> x; u--;
      ll ans = rq.prod(hld.rangeL[u], hld.rangeR[u]);
      cout << ans << "\n";
    }
  }
  return 0;
}


struct ios_do_not_sync{
  ios_do_not_sync(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
  }
} ios_do_not_sync_instance;
0