結果

問題 No.1038 TreeAddQuery
ユーザー beetbeet
提出日時 2023-12-10 23:18:32
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 4,329 bytes
コンパイル時間 3,151 ms
コンパイル使用メモリ 219,792 KB
最終ジャッジ日時 2025-02-18 10:08:30
ジャッジサーバーID
(参考情報)
judge2 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 5 TLE * 1 -- * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

// verification-helper: PROBLEM https://yukicoder.me/problems/3912
#include<bits/stdc++.h>
using namespace std;
#define call_from_test
struct Centroid{
inline static mt19937 mt;
vector<int> dead;
vector< vector<int> > G;
Centroid(int n):dead(n,0),G(n){}
void add_edge(int u,int v){
G[u].emplace_back(v);
G[v].emplace_back(u);
}
void dfs(int v,int p,vector<int>& cs){
for(int u:G[v]){
if(dead[u]) continue;
cs.emplace_back(v);
if(u!=p) dfs(u,v,cs);
}
if(cs.empty()) cs.emplace_back(v);
}
vector<int> build(int r) {
vector<int> cs;
dfs(r,-1,cs);
shuffle(cs.begin(),cs.end(),mt);
cs.resize(1);
return cs;
}
const vector<int>& operator[](int k)const{return G[k];}
void disable(int v){dead[v]=1;}
void enable(int v){dead[v]=0;}
int alive(int v){return !dead[v];}
};
template<typename F>
struct FixPoint : F{
FixPoint(F&& f):F(forward<F>(f)){}
template<typename... Args>
decltype(auto) operator()(Args&&... args) const{
return F::operator()(*this,forward<Args>(args)...);
}
};
template<typename F>
inline decltype(auto) MFP(F&& f){
return FixPoint<F>{forward<F>(f)};
}
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
template <typename E>
struct SegmentTree{
using H = function<E(E,E)>;
int n,height;
H h;
E ei;
vector<E> laz;
SegmentTree(H h,E ei):h(h),ei(ei){}
void init(int n_){
n=1;height=0;
while(n<n_) n<<=1,height++;
laz.assign(2*n,ei);
}
inline void propagate(int k){
if(laz[k]==ei) return;
laz[(k<<1)|0]=h(laz[(k<<1)|0],laz[k]);
laz[(k<<1)|1]=h(laz[(k<<1)|1],laz[k]);
laz[k]=ei;
}
inline void thrust(int k){
for(int i=height;i;i--) propagate(k>>i);
}
void update(int a,int b,E x){
if(a>=b) return;
thrust(a+=n);
thrust(b+=n-1);
for(int l=a,r=b+1;l<r;l>>=1,r>>=1){
if(l&1) laz[l]=h(laz[l],x),l++;
if(r&1) --r,laz[r]=h(laz[r],x);
}
}
E get_val(int a){
thrust(a+=n);
return laz[a];
}
void set_val(int a,E x){
thrust(a+=n);
laz[a]=x;
}
};
#undef call_from_test
signed main(){
cin.tie(0);
ios::sync_with_stdio(0);
int n,q;
cin>>n>>q;
Centroid G(n);
for(int i=1;i<n;i++){
int a,b;
cin>>a>>b;
a--;b--;
G.add_edge(a,b);
}
vector<int> xs(q),ys(q),zs(q);
for(int i=0;i<q;i++) cin>>xs[i]>>ys[i]>>zs[i];
vector<vector<int>> H(n);
for(int i=0;i<q;i++){
xs[i]--;
H[xs[i]].emplace_back(i);
}
vector<int> dep(n);
using ll = long long;
vector<ll> ans(q,0);
auto h=[&](ll a,ll b){return a+b;};
SegmentTree<ll> seg(h,0);
seg.init(n*2);
queue<int> que;
que.emplace(G.build(0)[0]);
while(!que.empty()){
int r=que.front();que.pop();
dep[r]=0;
// add for all
{
int len=1;
vector<int> qs(H[r]);
for(int t:G[r]){
if(!G.alive(t)) continue;
MFP([&](auto dfs,int v,int p,int d)->void{
dep[v]=d;
chmax(len,d+1);
for(int i:H[v]) qs.emplace_back(i);
for(int u:G[v]){
if(u==p) continue;
if(!G.alive(u)) continue;
dfs(u,v,d+1);
}
})(t,r,1);
}
seg.init(len);
sort(qs.begin(),qs.end());
for(int i:qs){
ans[i]+=seg.get_val(dep[xs[i]]);
if(ys[i]>=dep[xs[i]])
seg.update(0,min(len,ys[i]-dep[xs[i]]+1),zs[i]);
}
}
// sub for subtree
{
for(int t:G[r]){
if(!G.alive(t)) continue;
int len=1;
vector<int> qs;
MFP([&](auto dfs,int v,int p,int d)->void{
dep[v]=d;
chmax(len,d+1);
for(int i:H[v]) qs.emplace_back(i);
for(int u:G[v]){
if(u==p) continue;
if(!G.alive(u)) continue;
dfs(u,v,d+1);
}
})(t,r,1);
seg.init(len);
sort(qs.begin(),qs.end());
for(int i:qs){
ans[i]-=seg.get_val(dep[xs[i]]);
if(ys[i]>=dep[xs[i]])
seg.update(0,min(len,ys[i]-dep[xs[i]]+1),zs[i]);
}
}
}
G.disable(r);
for(int t:G[r])
if(G.alive(t))
que.emplace(G.build(t)[0]);
}
for(auto a:ans) cout<<a<<"\n";
cout<<flush;
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0