結果
| 問題 | No.1038 TreeAddQuery |
| ユーザー |
👑  tute7627
|
| 提出日時 | 2020-08-24 18:37:20 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 2,489 ms / 4,000 ms |
| コード長 | 7,483 bytes |
| コンパイル時間 | 3,907 ms |
| コンパイル使用メモリ | 254,128 KB |
| 実行使用メモリ | 226,684 KB |
| 最終ジャッジ日時 | 2024-11-06 10:34:23 |
| 合計ジャッジ時間 | 33,596 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
6,816 KB |
| testcase_01 | AC | 2 ms
6,820 KB |
| testcase_02 | AC | 3 ms
6,816 KB |
| testcase_03 | AC | 12 ms
6,816 KB |
| testcase_04 | AC | 12 ms
6,820 KB |
| testcase_05 | AC | 13 ms
6,820 KB |
| testcase_06 | AC | 11 ms
6,816 KB |
| testcase_07 | AC | 13 ms
6,820 KB |
| testcase_08 | AC | 1,439 ms
140,796 KB |
| testcase_09 | AC | 1,625 ms
148,540 KB |
| testcase_10 | AC | 1,762 ms
150,328 KB |
| testcase_11 | AC | 1,617 ms
148,208 KB |
| testcase_12 | AC | 1,667 ms
148,936 KB |
| testcase_13 | AC | 2,489 ms
226,560 KB |
| testcase_14 | AC | 1,915 ms
162,780 KB |
| testcase_15 | AC | 1,861 ms
157,832 KB |
| testcase_16 | AC | 1,928 ms
155,020 KB |
| testcase_17 | AC | 1,816 ms
153,436 KB |
| testcase_18 | AC | 365 ms
61,292 KB |
| testcase_19 | AC | 449 ms
72,708 KB |
| testcase_20 | AC | 476 ms
73,840 KB |
| testcase_21 | AC | 505 ms
73,588 KB |
| testcase_22 | AC | 761 ms
98,204 KB |
| testcase_23 | AC | 847 ms
100,300 KB |
| testcase_24 | AC | 1,288 ms
147,068 KB |
| testcase_25 | AC | 2,380 ms
226,684 KB |
| testcase_26 | AC | 1,344 ms
146,952 KB |
ソースコード
//#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;
}