結果

問題 No.2163 LCA Sum Query
ユーザー snukesnuke
提出日時 2022-12-16 21:53:37
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 763 ms / 6,000 ms
コード長 8,778 bytes
コンパイル時間 2,755 ms
コンパイル使用メモリ 220,712 KB
実行使用メモリ 17,148 KB
最終ジャッジ日時 2023-08-10 03:45:15
合計ジャッジ時間 20,078 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 3 ms
4,380 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 2 ms
4,380 KB
testcase_11 AC 3 ms
4,380 KB
testcase_12 AC 251 ms
4,512 KB
testcase_13 AC 352 ms
13,992 KB
testcase_14 AC 233 ms
14,760 KB
testcase_15 AC 95 ms
4,376 KB
testcase_16 AC 203 ms
14,160 KB
testcase_17 AC 221 ms
8,480 KB
testcase_18 AC 158 ms
4,668 KB
testcase_19 AC 112 ms
4,376 KB
testcase_20 AC 16 ms
8,764 KB
testcase_21 AC 105 ms
8,896 KB
testcase_22 AC 563 ms
15,060 KB
testcase_23 AC 457 ms
15,220 KB
testcase_24 AC 529 ms
14,920 KB
testcase_25 AC 460 ms
14,984 KB
testcase_26 AC 763 ms
14,900 KB
testcase_27 AC 584 ms
14,900 KB
testcase_28 AC 743 ms
14,868 KB
testcase_29 AC 595 ms
14,996 KB
testcase_30 AC 260 ms
16,908 KB
testcase_31 AC 261 ms
17,148 KB
testcase_32 AC 266 ms
16,328 KB
testcase_33 AC 241 ms
16,888 KB
testcase_34 AC 274 ms
14,988 KB
testcase_35 AC 219 ms
15,104 KB
testcase_36 AC 263 ms
15,004 KB
testcase_37 AC 212 ms
14,996 KB
testcase_38 AC 311 ms
15,696 KB
testcase_39 AC 276 ms
15,720 KB
testcase_40 AC 309 ms
15,576 KB
testcase_41 AC 265 ms
15,748 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rep1(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < (t); ++i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define pob pop_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define newline puts("")
using namespace std;
template<typename T> using vc = vector<T>;
template<typename T> using vv = vc<vc<T>>;
template<typename T> using PQ = priority_queue<T,vc<T>,greater<T>>;
using uint = unsigned; using ull = unsigned long long;
using vi = vc<int>; using vvi = vv<int>; using vvvi = vv<vi>;
using ll = long long; using vl = vc<ll>; using vvl = vv<ll>; using vvvl = vv<vl>;
using P = pair<int,int>; using vp = vc<P>; using vvp = vv<P>;
int geti(){int x;scanf("%d",&x);return x;}
vi pm(int n, int s=0) { vi a(n); iota(rng(a),s); return a;}
template<typename T>istream& operator>>(istream&i,vc<T>&v){rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(const T&v,const string& d=""){stringstream s;rep(i,sz(v))(i?s<<d:s)<<v[i];return s.str();}
template<typename T>ostream& operator<<(ostream&o,const vc<T>&v){if(sz(v))o<<join(v," ");return o;}
template<typename T1,typename T2>istream& operator>>(istream&i,pair<T1,T2>&v){return i>>v.fi>>v.se;}
template<typename T1,typename T2>ostream& operator<<(ostream&o,const pair<T1,T2>&v){return o<<v.fi<<","<<v.se;}
template<typename T1,typename T2>void operator--(pair<T1,T2>&a,int){a.fi--;a.se--;}
template<typename T>void operator--(vc<T>&a,int){for(T&x:a)x--;}
template<typename T>void operator++(vc<T>&a,int){for(T&x:a)x++;}
template<typename T>void operator+=(vc<T>&a,T b){for(T&x:a)x+=b;}
template<typename T>void operator+=(vc<T>&a,const vc<T>&b){a.insert(a.end(),rng(b));}
template<typename T1,typename T2>bool mins(T1& x,const T2&y){if(x>y){x=y;return true;}else return false;}
template<typename T1,typename T2>bool maxs(T1& x,const T2&y){if(x<y){x=y;return true;}else return false;}
template<typename Tx, typename Ty>Tx dup(Tx x, Ty y){return (x+y-1)/y;}
template<typename T>ll suma(const vc<T>&a){ll res(0);for(auto&&x:a)res+=x;return res;}
template<typename T>ll suma(const vv<T>&a){ll res(0);for(auto&&x:a)res+=suma(x);return res;}
template<typename T>void uni(T& a){sort(rng(a));a.erase(unique(rng(a)),a.end());}
template<typename T>void prepend(vc<T>&a,const T&x){a.insert(a.begin(),x);}
const double eps = 1e-10;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#define dame { puts("-1"); return;}
#define yes { puts("Yes"); return;}
#define no { puts("No"); return;}
#define ret(x) { cout<<(x)<<endl; return;}
#define yn {puts("Yes");}else{puts("No");}
const int MX = 200005;

// Binary Indexed Tree
template<typename T=int>
struct bit {
  int n; vector<T> d;
  bit() {}
  bit(int mx): n(mx+1), d(mx+1) {}
  void add(int i, T x=1) {
    for (++i;i<n;i+=i&-i) d[i] += x;
  }
  T sum(int i) {
    T x = 0;
    for (++i;i;i-=i&-i) x += d[i];
    return x;
  }
  T sum(int l, int r) { return sum(r-1)-sum(l-1);}
};
//

// Segment tree with lazy prop
struct F {
  ll s, cs;
  F(ll s=0, ll cs=0):s(s),cs(cs) {}
  F& operator+=(const F& f) {
    s += f.s;
    cs += f.cs;
    return *this;
  }
  F operator+(const F& f) const { return F(*this) += f;}
};
ostream& operator<<(ostream&o,const F&f){return o<<f.s<<','<<f.cs;}
struct G {
  int x;
  G(int x=0):x(x) {}
  void operator()(F& f) const {
    f.s += f.cs*x;
  }
  void operator*=(const G& g) {
    x += g.x;
  }
};
ostream& operator<<(ostream&o,const G&g){return o<<g.x;}

struct F2 {
  ll s2, s1, w;
  F2(ll s2=0, ll s1=0, ll w=0):s2(s2),s1(s1),w(w) {}
  F2& operator+=(const F2& f) {
    s2 += f.s2;
    s1 += f.s1;
    w += f.w;
    return *this;
  }
  F2 operator+(const F2& f) const { return F2(*this) += f;}
};
ostream& operator<<(ostream&o,const F2&f){return o<<f.s2<<','<<f.s1;}
struct G2 {
  int x;
  G2(int x=0):x(x) {}
  void operator()(F2& f) const {
    f.s2 += (f.s1*2 + f.w*x)*x;
    f.s1 += f.w*x;
  }
  void operator*=(const G2& g) {
    x += g.x;
  }
};
ostream& operator<<(ostream&o,const G2&g){return o<<g.x;}

template<typename F, typename G>
struct seg {
  struct FG {
    F f; G g;
    void apply(const G& _g) {
      _g(f);
      g *= _g;
    }
  };
  vector<FG> d; int n;
  seg(){}
  seg(int mx) {
    n = 1; while (n < mx) n <<= 1;
    d = vector<FG>(n<<1);
  }
  int width(int i) { return 1<<(__builtin_clz(i)-__builtin_clz(n));}
  void upd(int i) { d[i].f = d[i<<1].f+d[i<<1|1].f;}
  FG& operator[](int i) { return d[n+i];}
  void init() { drep(i,n) upd(i);}
  void prop(int i) {
    d[i<<1].apply(d[i].g);
    d[i<<1|1].apply(d[i].g);
    d[i].g = G();
  }
  void add(int l, int r, G g) { if (l < r) add(l,r,g,1,0,n);}
  void add(int a, int b, const G& g, int i, int l, int r) {
    if (a <= l && r <= b) {
      d[i].apply(g);
      return;
    }
    prop(i);
    int c = (l+r)>>1;
    if (a < c) add(a,b,g,i<<1,l,c);
    if (c < b) add(a,b,g,i<<1|1,c,r);
    upd(i);
  }
  void add(int v, F f) {
    int i = 1;
    for (int b = n; i < n; b >>= 1, i = i<<1|!!(v&b)) prop(i);
    d[i].f += f;
    while (i > 1) i >>= 1, upd(i);
  }
  F get(int l, int r) { return (l < r) ? get(l,r,1,0,n) : F();}
  F get(int a, int b, int i, int l, int r) {
    if (a <= l && r <= b) return d[i].f;
    prop(i);
    int c = (l+r)>>1;
    F res;
    if (a < c) res += get(a,b,i<<1,l,c);
    if (c < b) res += get(a,b,i<<1|1,c,r);
    return res;
  }
  void print() {
    srep(i,1,n*2) cerr<<d[i].f<<' ';
    cerr << endl;
    srep(i,1,n*2) cerr<<d[i].g<<' ';
    cerr << endl;
  }
};
//

// HL-decomposition
struct hl {
  int n, root, tot;
  vvi to;
  seg<F,G> t;
  seg<F2,G2> t2;
  bit<int> nt;
  hl(int n=0):n(n),to(n) {}
  void addEdge(int a, int b) {
    to[a].pb(b);
    to[b].pb(a);
  }
  vi tsz, pa, dep;
  int tfs(int v, int p=-1) {
    pa[v] = p;
    tsz[v] = 1;
    rep(i,sz(to[v])) {
      int& u = to[v][i];
      if (u == p) swap(u, to[v].back());
      if (u == p) break;
      dep[u] = dep[v]+1;
      tsz[v] += tfs(u,v);
      if (tsz[u] > tsz[to[v][0]]) swap(u, to[v][0]);
    }
    if (~p) to[v].pop_back();
    return tsz[v];
  }
  vi in, out, nxt, kv;
  void dfs(int v) {
    in[v] = sz(kv); kv.pb(v);
    rep(i,sz(to[v])) {
      int u = to[v][i];
      nxt[u] = i ? u : nxt[v];
      dfs(u);
    }
    out[v] = sz(kv);
  }
  void init(int v=0) {
    tsz = pa = dep = vi(n);
    tfs(root = v);
    in = out = nxt = vi(n);
    nxt[root] = root;
    dfs(root);
    t = seg<F,G>(n);
    t2 = seg<F2,G2>(n);
    rep(i,n) if (i != v) t2[in[i]].f.w = i-pa[i];
    t2.init();
    nt = bit(n);
    tot = 0;
  }
  int up(int v, int l) {
    while (~v) {
      int u = nxt[v], nl = dep[v]-dep[u]+1;
      if (l < nl) return kv[in[v]-l];
      l -= nl; v = pa[u];
    }
    return -1;
  }
  int lca(int a, int b) {
    while (nxt[a] != nxt[b]) {
      if (in[a] < in[b]) swap(a,b);
      a = pa[nxt[a]];
    }
    if (in[a] < in[b]) swap(a,b);
    return b;
  }
  int len(int a, int b) { return dep[a]+dep[b]-dep[lca(a,b)]*2;}

  //* // SEG
  int num(int v) {
    return nt.sum(in[v], out[v]);
  }
  void add(int v, int co=1) {
    int _v = v;
    if (co == -1) nt.add(in[_v],-1);

    int pc = 0;
    while (~v) {
      int u = nxt[v];
      t.add(in[v], F(ll(num(v)-pc)*(v+1)*co, (v+1)*co));
      t.add(in[u], in[v], G(co));
      t2.add(in[u], in[v]+1, G2(co));
      v = pa[u];
      pc = num(u);
    }

    if (co == 1) nt.add(in[_v],1);
    tot += co;
  }

  ll getr(int v) { return t.get(in[v], out[v]).s;}
  ll getv(int v) {
    ll res = getr(0);
    if (v) {
      F2 f;
      while (~v) {
        int u = nxt[v];
        f += t2.get(in[u], in[v]+1);
        v = pa[u];
      }
      res += f.s1*tot - f.s2;
    }
    return res;
  }
  ll get(int r, int v) {
    if (lca(r,v) != v) return getr(v);
    ll res = getv(v);
    if (v == r) return res;
    r = up(r, dep[r]-dep[v]-1);
    res -= getr(r);
    int c = num(r);
    res -= ll(v+1)*c*(tot-c);
    return res;
  }
  //*/
};
//

struct Solver {
  void solve() {
    int n,q;
    scanf("%d%d",&n,&q);

    hl t(n);
    rep(i,n-1) {
      int a,b;
      scanf("%d%d",&a,&b);
      --a; --b;
      t.addEdge(a,b);
    }
    t.init();

    vi c(n);
    rep(qi,q) {
      int u,r,v;
      scanf("%d%d%d",&u,&r,&v);
      --u; --r; --v;
      t.add(u, c[u]?-1:1);
      c[u] ^= 1;

      ll ans = t.get(r,v);
      printf("%lld\n",ans);
    }
  }
};

int main() {
  // cin.tie(nullptr); ios::sync_with_stdio(false);
  int ts = 1;
  // scanf("%d",&ts);
  rep1(ti,ts) {
    Solver solver;
    solver.solve();
  }
  return 0;
}
0