結果
| 問題 | No.1038 TreeAddQuery |
| ユーザー |
 tko919
|
| 提出日時 | 2022-10-19 23:03:41 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,611 ms / 4,000 ms |
| コード長 | 12,553 bytes |
| コンパイル時間 | 3,097 ms |
| コンパイル使用メモリ | 228,932 KB |
| 最終ジャッジ日時 | 2025-02-08 08:24:01 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 24 |
ソースコード
#line 1 "library/Template/template.hpp"#include <bits/stdc++.h>using namespace std;#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)#define ALL(v) (v).begin(),(v).end()using ll=long long int;const int inf = 0x3fffffff;const ll INF = 0x1fffffffffffffff;template<typename T>inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}template<typename T>inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}#line 2 "library/Utility/fastio.hpp"#include <unistd.h>class FastIO{static constexpr int L=1<<16;char rdbuf[L];int rdLeft=0,rdRight=0;inline void reload(){int len=rdRight-rdLeft;memmove(rdbuf,rdbuf+rdLeft,len);rdLeft=0,rdRight=len;rdRight+=fread(rdbuf+len,1,L-len,stdin);}inline bool skip(){for(;;){while(rdLeft!=rdRight and rdbuf[rdLeft]<=' ')rdLeft++;if(rdLeft==rdRight){reload();if(rdLeft==rdRight)return false;}else break;}return true;}template<typename T,enable_if_t<is_integral<T>::value,int> =0>inline bool _read(T& x){if(!skip())return false;if(rdLeft+20>=rdRight)reload();bool neg=false;if(rdbuf[rdLeft]=='-'){neg=true;rdLeft++;}x=0;while(rdbuf[rdLeft]>='0' and rdLeft<rdRight){x=x*10+(neg?-(rdbuf[rdLeft++]^48):(rdbuf[rdLeft++]^48));}return true;}template<typename T,enable_if_t<is_floating_point<T>::value,int> =0>inline bool _read(T& x){if(!skip())return false;if(rdLeft+20>=rdRight)reload();bool neg=false;if(rdbuf[rdLeft]=='-'){neg=true;rdLeft++;}x=0;while(rdbuf[rdLeft]>='0' and rdbuf[rdLeft]<='9' and rdLeft<rdRight){x=x*10+(rdbuf[rdLeft++]^48);}if(rdbuf[rdLeft]!='.')return true;rdLeft++;T base=.1;while(rdbuf[rdLeft]>='0' and rdbuf[rdLeft]<='9' and rdLeft<rdRight){x+=base*(rdbuf[rdLeft++]^48);base*=.1;}if(neg)x=-x;return true;}inline bool _read(char& x){if(!skip())return false;if(rdLeft+1>=rdRight)reload();x=rdbuf[rdLeft++];return true;}inline bool _read(string& x){if(!skip())return false;for(;;){int pos=rdLeft;while(pos<rdRight and rdbuf[pos]>' ')pos++;x.append(rdbuf+rdLeft,pos-rdLeft);if(rdLeft==pos)break;rdLeft=pos;if(rdLeft==rdRight)reload();else break;}return true;}template<typename T>inline bool _read(vector<T>& v){for(auto& x:v){if(!_read(x))return false;}return true;}char wtbuf[L],tmp[50];int wtRight=0;inline void flush(){fwrite(wtbuf,1,wtRight,stdout);wtRight=0;}inline void _write(const char& x){if(wtRight>L-32)flush();wtbuf[wtRight++]=x;}inline void _write(const string& x){for(auto& c:x)_write(c);}template<typename T,enable_if_t<is_integral<T>::value,int> =0>inline void _write(T x){if(wtRight>L-32)flush();if(x==0){_write('0');return;}else if(x<0){_write('-');if (__builtin_expect(x == std::numeric_limits<T>::min(), 0)) {switch (sizeof(x)) {case 2: _write("32768"); return;case 4: _write("2147483648"); return;case 8: _write("9223372036854775808"); return;}}x=-x;}int pos=0;while(x!=0){tmp[pos++]=char((x%10)|48);x/=10;}rep(i,0,pos)wtbuf[wtRight+i]=tmp[pos-1-i];wtRight+=pos;}template<typename T>inline void _write(const vector<T>& v){rep(i,0,v.size()){if(i)_write(' ');_write(v[i]);}}public:FastIO(){}~FastIO(){flush();}inline void read(){}template <typename Head, typename... Tail>inline void read(Head& head,Tail&... tail){assert(_read(head));read(tail...);}template<bool ln=true,bool space=false>inline void write(){if(ln)_write('\n');}template <bool ln=true,bool space=false,typename Head, typename... Tail>inline void write(const Head& head,const Tail&... tail){if(space)_write(' ');_write(head);write<ln,true>(tail...);}};/*** @brief Fast IO*/#line 3 "sol.cpp"#line 2 "library/Graph/centroid.hpp"class CentroidDecomposition{void get(int v,int p){sz[v]=1;for(auto& to:g[v])if(to!=p and !used[to]){get(to,v);sz[v]+=sz[to];}}int dfs(int v,int p,int rt){for(auto& to:g[v])if(to!=p and !used[to]){if(sz[to]>(sz[rt]>>1))return dfs(to,v,rt);}return v;}public:int n;vector<vector<int>> g;vector<int> sz,used;CentroidDecomposition(int n_):n(n_),g(n),sz(n),used(n){}void add_edge(int u,int v){g[u].push_back(v);g[v].push_back(u);}int find(int rt){get(rt,-1);int res=dfs(rt,-1,rt);used[res]=1;return res;}};/*** @brief Centroid Decomposition*/#line 2 "library/Graph/hld.hpp"struct HLD{using P=pair<int,int>;vector<vector<int>> g; vector<int> sz,in,out,rev,hs,par,dist;void dfs(int v,int p){par[v]=p; sz[v]=1; dist[v]=dist[p]+1;if(!g[v].empty() and g[v][0]==p)swap(g[v][0],g[v].back());for(auto& to:g[v])if(to!=p){dfs(to,v); sz[v]+=sz[to];if(sz[g[v][0]]<sz[to])swap(g[v][0],to);}}void dfs2(int v,int p,int& k){in[v]=k++; rev[in[v]]=v;for(auto& to:g[v])if(to!=p){hs[to]=(g[v][0]==to?hs[v]:to);dfs2(to,v,k);}out[v]=k;}HLD(int _n):g(_n),sz(_n),in(_n),out(_n),rev(_n),hs(_n),par(_n),dist(_n){}void add_edge(int u,int v){g[u].emplace_back(v); g[v].emplace_back(u);}void run(int rt=0){dfs(rt,-1); hs[rt]=rt; int k=0; dfs2(rt,-1,k);}int lca(int u,int v){for(;;v=par[hs[v]]){if(in[u]>in[v])swap(u,v);if(hs[u]==hs[v])return u;}}vector<P> get(int u,int p,bool es=0){assert(in[p]<=in[u] and out[u]<=out[p]);vector<P> res;while(hs[u]!=hs[p]){res.push_back({in[hs[u]],in[u]+1});u=par[hs[u]];}res.push_back({in[p]+es,in[u]+1});return res;}int jump(int u,int v,int k){if(k<0)return -1;int g=lca(u,v);int d0=dist[u]+dist[v]-dist[g]*2;if(d0<k)return -1;int st=u;if(dist[u]-dist[g]<k)st=v,k=d0-k;for(;;){int to=hs[st];if(in[st]-k>=in[to])return rev[in[st]-k];k-=in[st]-in[to]+1; st=par[to];}}};/*** @brief Heavy Light Decomposition*/#line 6 "sol.cpp"struct ContourQuery{using P=pair<int,int>;using T=pair<int,P>;ContourQuery(int _n=0):n(_n),m(_n),cd(_n),hld(_n),tree(_n*3),depth(_n*3),base(_n*3),parent(_n*3,-1),SZ(_n*3),width(_n*3,1),seg(_n*3){}void add_edge(int u,int v){cd.add_edge(u,v);hld.add_edge(u,v);}vector<int> run(){hld.run();root=rec(0);depth[0]=0;dfs(0,-1);rep(v,0,m)if(v!=root){seg[v]=width[v];}return seg;}vector<P> point(int v){vector<P> ret;int cur=v;while(cur!=root){int D=depth[v]+depth[base[cur]]-2*depth[hld.lca(v,base[cur])];ret.push_back({cur,D});cur=parent[cur];}return ret;}vector<T> range(int v,int L,int R){vector<T> ret;if(L<=0 and 0<R)ret.push_back({v,{0,1}});int cur=parent[v],pre=v;while(pre!=root){int bro=-1;for(auto& to:tree[cur])if(to!=parent[cur] and to!=pre){bro=to;break;}if(bro!=-1){int D=depth[v]+depth[base[bro]]-2*depth[hld.lca(v,base[bro])];ret.push_back({bro,{clamp(L-D,0,seg[bro]),clamp(R-D,0,seg[bro])}});}pre=cur;cur=parent[cur];}return ret;}private:int n,m,root;CentroidDecomposition cd;HLD hld;vector<vector<int>> tree;vector<int> depth,base,parent,SZ,width,seg;int rec(int rt){int cen=cd.find(rt);SZ[cen]=1;queue<P> que;auto cmp=[&](int u,int v){return SZ[u]>SZ[v];};priority_queue<int,vector<int>,decltype(cmp)> pq{cmp};pq.push(cen);depth[cen]=0;base[cen]=cen;for(auto& to:cd.g[cen])if(!cd.used[to]){int v=rec(to);que.push({to,cen});depth[to]=1;while(!que.empty()){auto [cur,par]=que.front();que.pop();width[v]=depth[cur]+1;for(auto& nxt:cd.g[cur])if(nxt!=par and !cd.used[nxt]){depth[nxt]=depth[cur]+1;que.push({nxt,cur});}}pq.push(v);base[v]=cen;}cd.used[cen]=0;if(pq.size()>1){for(;;){int v1=pq.top();pq.pop();int v2=pq.top();pq.pop();int extra=m++;tree[extra].push_back(v1);tree[extra].push_back(v2);tree[v1].push_back(extra);tree[v2].push_back(extra);SZ[extra]=SZ[v1]+SZ[v2];parent[v1]=parent[v2]=extra;if(pq.empty()){return extra;}pq.push(extra);base[extra]=cen;width[extra]=max(width[v1],width[v2]);}}else{int extra=m++;tree[extra].push_back(cen);tree[cen].push_back(extra);SZ[extra]=1;parent[cen]=extra;return extra;}}void dfs(int v,int p){for(auto& to:cd.g[v])if(to!=p){depth[to]=depth[v]+1;dfs(to,v);}}};#line 2 "library/DataStructure/dualsegtree.hpp"template<typename M,M (*f)(M,M),M (*m1)()>class DualSegmentTree{int sz,height;vector<M> data;void down(int k){data[k*2]=f(data[k*2],data[k]);data[k*2+1]=f(data[k*2+1],data[k]);data[k]=m1();}public:DualSegmentTree(){}DualSegmentTree(int n){sz=1,height=0;while(sz<n)sz<<=1,height++;data.assign(2*sz,m1());}void run(vector<M>& v){for(int i=0;i<(int)v.size();i++)data[i+sz]=v[i];}void update(int a,int b,M x){if(a>=b)return;a+=sz,b+=sz;for(int i=height;i;i--){if(((a>>i)<<i)!=a)down(a>>i);if(((b>>i)<<i)!=b)down((b-1)>>i);}for(;a<b;a>>=1,b>>=1){if(a&1)data[a]=f(data[a],x),a++;if(b&1)--b,data[b]=f(data[b],x);}}M query(int k){k+=sz;for(int i=height;i;i--){if(((k>>i)<<i)!=k)down(k>>i);}M ret=data[k];while(k>>=1)ret=f(ret,data[k]);return ret;}};/*** @brief Dual Segment Tree*/#line 127 "sol.cpp"ll f(ll a,ll b){return a+b;}ll m1(){return 0;}FastIO io;int main(){int n,q;io.read(n,q);ContourQuery buf(n);rep(_,0,n-1){int a,b;io.read(a,b);a--; b--;buf.add_edge(a,b);}auto len=buf.run();vector<DualSegmentTree<ll,f,m1>> seg(len.size());rep(i,0,len.size())seg[i]=DualSegmentTree<ll,f,m1>(len[i]);while(q--){int x,y,z;io.read(x,y,z);x--;ll ret=0;for(auto& [i,v]:buf.point(x)){ret+=seg[i].query(v);}io.write(ret);for(auto& [i,LR]:buf.range(x,0,y+1)){auto [L,R]=LR;seg[i].update(L,R,z);}}return 0;}