結果
| 問題 | No.1038 TreeAddQuery |
| ユーザー |
👑  tute7627
|
| 提出日時 | 2020-08-24 18:37:20 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,947 ms / 4,000 ms |
| コード長 | 7,483 bytes |
| コンパイル時間 | 4,239 ms |
| コンパイル使用メモリ | 241,496 KB |
| 最終ジャッジ日時 | 2025-01-13 13:32:51 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 24 |
ソースコード
//#define _GLIBCXX_DEBUG#include<bits/stdc++.h>using namespace std;#define endl '\n'#define lfs cout<<fixed<<setprecision(10)#define ALL(a) (a).begin(),(a).end()#define ALLR(a) (a).rbegin(),(a).rend()#define spa << " " <<#define fi first#define se second#define MP make_pair#define MT make_tuple#define PB push_back#define EB emplace_back#define rep(i,n,m) for(ll i = (n); i < (ll)(m); i++)#define rrep(i,n,m) for(ll i = (ll)(m) - 1; i >= (ll)(n); i--)using ll = long long;using ld = long double;const ll MOD1 = 1e9+7;const ll MOD9 = 998244353;const ll INF = 1e18;using P = pair<ll, ll>;template<typename T1, typename T2>bool chmin(T1 &a,T2 b){if(a>b){a=b;return true;}else return false;}template<typename T1, typename T2>bool chmax(T1 &a,T2 b){if(a<b){a=b;return true;}else return false;}ll median(ll a,ll b, ll c){return a+b+c-max({a,b,c})-min({a,b,c});}void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}template<typename T1,typename T2>void ans(bool x,T1 y,T2 z){if(x)cout<<y<<endl;else cout<<z<<endl;}template<typename T>void debug(vector<vector<T>>&v,ll h,ll w){for(ll i=0;i<h;i++){cout<<v[i][0];for(ll j=1;j<w;j++)cout spa v[i][j];cout<<endl;}};void debug(vector<string>&v,ll h,ll w){for(ll i=0;i<h;i++){for(ll j=0;j<w;j++)cout<<v[i][j];cout<<endl;}};template<typename T>void debug(vector<T>&v,ll n){if(n!=0)cout<<v[0];for(ll i=1;i<n;i++)cout spa v[i];cout<<endl;};template<typename T>vector<vector<T>>vec(ll x, ll y, T w){vector<vector<T>>v(x,vector<T>(y,w));return v;}ll gcd(ll x,ll y){ll r;while(y!=0&&(r=x%y)!=0){x=y;y=r;}return y==0?x:y;}vector<ll>dx={1,-1,0,0,1,1,-1,-1};vector<ll>dy={0,0,1,-1,1,-1,1,-1};template<typename T>vector<T> make_v(size_t a,T b){return vector<T>(a,b);}template<typename... Ts>auto make_v(size_t a,Ts... ts){return vector<decltype(make_v(ts...))>(a,make_v(ts...));}template<typename T1, typename T2>ostream &operator<<(ostream &os, const pair<T1, T2>&p){return os << p.first << " " << p.second;}template<typename T>ostream &operator<<(ostream &os, const vector<T> &v){for(auto &z:v)os << z << " ";cout<<"|"; return os;}//mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());struct edge{ll to=-1;edge(){};edge(ll t):to(t){};};struct CentroidDecomposition{ll n;const vector<vector<edge>> &g;vector<bool> used;//既に重心として選ばれたかvector<ll> sub;//部分木のサイズCentroidDecomposition(const vector<vector<edge>> &g):g(g){n = g.size();sub.assign(g.size(), 0);used.assign(g.size(), false);}ll search_centroid(ll root){return dfs_search(root, -1, dfs_sz(root, -1) / 2 );}ll dfs_sz(ll k, ll par){sub[k] = 1;for(auto e:g[k]){if(e.to == par || used[e.to])continue;sub[k] += dfs_sz(e.to, k);}return sub[k];}ll dfs_search(ll k, ll par, ll mid){for(auto e:g[k]){if(e.to == par || used[e.to])continue;if(sub[e.to] > mid)return dfs_search(e.to, k, mid);}return k;}vector<ll> centroid_enum(ll root){vector<ll>ret;ret.push_back(search_centroid(root));for(auto e:g[ret[0]]){if(used[e.to] || n != 2 * sub[e.to])continue;ll c = search_centroid(e.to);if(c != ret[0]){ret.push_back(c);break;}}return ret;}vector<vector<ll>>belong;vector<ll>pr;void build_all(){belong.resize(n);pr.resize(n);build(0,0);}void build(ll root,ll num){ll cent = search_centroid(root);used[cent] = true;pr[cent]=num;build_dfs(cent, -1, cent);for(auto e:g[cent])if(!used[e.to])build(e.to,num+1);used[cent] = false;}void build_dfs(ll k,ll par,ll cent){belong[k].push_back(cent);for(auto e:g[k]){if(e.to == par || used[e.to])continue;build_dfs(e.to, k, cent);}}void run(){//何か前処理を書くならsolve(0);}void solve(ll root){ll cent = search_centroid(root);ll size = sub[root];used[cent] = true;vector<vector<ll>>ver;for(auto e:g[cent]){if(!used[e.to]){ver.emplace_back();dfs(e.to,-1,ver.back());}}for(auto e:g[cent]){if(!used[e.to]){solve(e.to);}}used[cent] = false;return;}void dfs(ll k,ll par,vector<ll>&ver){ver.push_back(k);for(auto e:g[k]){if(e.to==par||used[e.to])continue;dfs(e.to,k,ver);}}};template<typename T>struct BIT{ll n;ll k=1;vector<T>data;BIT() = default;BIT(ll size):n(size){n++;data.assign(n,0);while(k*2<=n)k*=2;}void add(ll a,T w){for(ll i=a+1;i<=n;i+=i&-i)data[i-1]+=w;}void add(ll l,ll r,T w){add(l,w);add(r+1,-w);}T sum(ll a){if(a<0)return 0;T ret = 0;for(ll i=a+1;i>0;i-=i&-i)ret+=data[i-1];return ret;}T sum(ll a,ll b){return a>b?0:sum(b)-sum(a-1);}T operator[](ll pos){return sum(pos,pos);}ll lower_bound(ll x){ll ret=0;for(ll i=k;i>0;i/=2){if(ret+i<=n&&data[ret+i-1]<x){x-=data[ret+i-1];ret+=i;}}return ret;}void print(){for(ll i=0;i<n;i++){if(i!=0)cout<<" ";cout<<sum(i);}cout<<endl;}};int main(){cin.tie(nullptr);ios_base::sync_with_stdio(false);ll res=0,buf=0;bool judge = true;ll n,q;cin>>n>>q;vector<vector<edge>>g(n);rep(i,0,n-1){ll u,v;cin>>u>>v;u--;v--;g[u].EB(v);g[v].EB(u);}CentroidDecomposition cent(g);cent.build_all();vector<BIT<ll>>bit(n);//距離順に並べたなにかvector<vector<BIT<ll>>>bit2(n);//距離順に並べたなにかusing TP=tuple<ll,ll,ll,ll,ll>;vector<vector<TP>>b(n);//(所属重心、方向、距離、BIT1のindex,BIT2のindex)vector<vector<vector<P>>>r(n);//[重心][方向][距離]=(BIT2上の範囲)vector<vector<P>>p(n);//[重心][距離]=(BIT上の範囲)auto &pr=cent.pr;rep(i,0,n){ll time=0;vector<ll>t;using TT=tuple<ll,ll,ll,ll>;//(頂点、方向、距離、親)queue<TT>que;que.emplace(i,-1,0,-1);while(!que.empty()){auto [v,dir,d,par]=que.front();que.pop();if(p[i].size()<=d)p[i].EB(time,time);else p[i][d].se=time;if(dir!=-1){if(r[i][dir].size()<=d)r[i][dir].EB(t[dir],t[dir]);else r[i][dir][d].se=t[dir];b[v].EB(i,dir,d,time,t[dir]);t[dir]++;}else b[v].EB(i,dir,d,time,-1);time++;for(auto e:g[v]){if(e.to==par||pr[i]>pr[e.to])continue;if(par==-1){r[i].emplace_back(1);t.push_back(0);que.emplace(e.to,++dir,d+1,v);}else que.emplace(e.to,dir,d+1,v);}}bit[i]=BIT<ll>(time);bit2[i].resize(t.size());rep(j,0,t.size())bit2[i][j]=BIT<ll>(t[j]);//debug(t,t.size());//debug(p[i],p[i].size());//debug(r[i],r[i].size());}while(q--){ll x,y,z;cin>>x>>y>>z;x--;ll ret=0;for(auto [c,dir,d,idx1,idx2]:b[x]){ret+=bit[c].sum(idx1);if(dir!=-1)ret-=bit2[c][dir].sum(idx2);d=y-d;//cout<<c spa dir spa d spa idx1 spa idx2<<endl;//bit[c].print();//bit[c].if(d<0)continue;bit[c].add(0,p[c][min(d,(ll)p[c].size()-1)].se,z);if(dir!=-1&&d!=0)bit2[c][dir].add(0,r[c][dir][min(d,(ll)r[c][dir].size()-1)].se,z);}cout<<ret<<endl;}return 0;}