#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include #include using namespace std; using namespace atcoder; using ll=long long; using P=pair; using T=tuple; struct S{ long long value; int size; }; using F = long long; S op(S a, S b){ return {a.value+b.value, a.size+b.size}; } S e(){ return {0, 0}; } S mapping(F f, S x){ return {x.value + f*x.size, x.size}; } F composition(F f, F g){ return f+g; } F id(){ return 0; } void IO(){ ios::sync_with_stdio(false); std::cin.tie(nullptr); } struct HLD{ //References: // https://judge.yosupo.jp/submission/72507 原典 // https://atcoder.jp/contests/abc294/submissions/39859050 原典より使いやすいsegtree対応ver // https://atcoder.jp/contests/past202010-open/submissions/33495220 原典より使いやすいlazy_segtree対応ver // ↑がReferencesの中で最もおすすめ //頂点に初期値を与える場合の注意点 // -hld.build()の実行後に行う // -頂点uはHLD内部ではhld.in[u]となる //辺に値がある場合は子側の頂点に持たせてedge=trueで関数を呼び出す //lazy_segtreeを使用 ll N,root; vector> G; vector parent;//頂点uの親 vector depth;//頂点uの深さ vector sz;//頂点uを根とする部分木のサイズ(heavy) vector in;//HLD時の探索順序(Euler Tour) vector out;//後述 vector head;//頂点uが属するHL分解後の連結成分の根 vector rev;//探索順序番号から元の頂点番号への逆引き ll t=0;//探索順序の計算用 //[in[u],out[u]) :=頂点uを根とする部分木に対応 //[in[head[u]],in[u]] :=HLD後の連結成分における頂点uからそのheadまでのパスに対応 HLD(){} HLD(ll n,ll r=0):N(n),root(r){ G.resize(N); parent.resize(N); depth.resize(N); sz.resize(N); in.resize(N); out.resize(N); head.resize(N); rev.resize(N); } //双方向に辺を張る void add_edge(ll u,ll v){ assert(0<=u&&u=in[v]){ return rev[in[u]-d]; } d-=in[u]-in[v]+1; u=parent[v]; } } //頂点u,vのLCA : O(log N) ll lca(ll u,ll v)const{ assert(0<=u&&uin[v]){ swap(u,v);//in[u]<=in[v] (uが根側) } if(head[u]==head[v]){ return u; } v=parent[head[v]]; } } //パス間の辺数 ll distance(ll u,ll v)const{ assert(0<=u&&u query(ll u,ll v,bool edge){ assert(0<=u&&u res; while(1){ if(in[u]>in[v]){ swap(u,v); } if(head[u]==head[v]){ break; } res.emplace_back(in[head[v]],in[v]); v=parent[head[v]]; } res.emplace_back(in[u]+edge,in[v]); return res; } //頂点uを根とする部分木に対する更新クエリ : O(log N) void apply_subtree(ll u,bool edge,function func){ assert(0<=u&&u S prod_subtree(ll u,bool edge,function func){ assert(0<=u&&u>n; vector

uv; vector edges; HLD hld(n); for(ll i=0;i>u>>v; u--; v--; uv.emplace_back(u,v); hld.add_edge(u,v); edges.emplace_back(u,v,0); } hld.build(); lazy_segtree seg(vector(n,{0,1})); for(ll i=0;i>q; bool edge=false; while(q--){ ll a,b; cin>>a>>b; a--; b--; vector

add_tax=hld.query(a,b,edge); for(auto pairs:add_tax){ ll l=pairs.first; ll r=pairs.second; seg.apply(l,r+1,1); } } ll ans=0; for(ll i=0;i