結果
| 問題 |
No.1038 TreeAddQuery
|
| コンテスト | |
| ユーザー |
 IKyopro
|
| 提出日時 | 2020-04-29 14:09:57 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,531 bytes |
| コンパイル時間 | 4,517 ms |
| コンパイル使用メモリ | 228,888 KB |
| 最終ジャッジ日時 | 2025-01-10 03:19:53 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 8 WA * 16 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class T, class U> using Pa = pair<T, U>;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;
template<typename Monoid,typename OperatorMonoid,typename F,typename G,typename H>
class LazySegmentTree {
private:
int sz,height;
vec<Monoid> data;
vec<OperatorMonoid> lazy;
const F op;
const G homo;
const H comp;
const Monoid e;
const OperatorMonoid Oe;
public:
LazySegmentTree(int n,const F op,const G homo,const H comp,
const Monoid &e,const OperatorMonoid Oe)
: op(op),homo(homo),comp(comp),e(e),Oe(Oe) {
sz = 1;
height = 0;
while(sz<=n) sz <<= 1,height++;
data.assign(2*sz,0);
lazy.assign(2*sz,Oe);
}
void renew(int n){
sz = 1;
height = 0;
while(sz<=n) sz <<= 1,height++;
fill(data.begin(),data.begin()+2*sz,0);
fill(lazy.begin(),lazy.begin()+2*sz,Oe);
}
void set(int k,const Monoid &x) {
data[k+sz] = x;
}
void build() {
for(int k=sz-1;k>0;k--) {
data[k] = op(data[2*k], data[2*k+1]);
}
}
inline void propagate(int k) {
if(lazy[k]!=Oe) {
lazy[2*k] = comp(lazy[2*k], lazy[k]);
lazy[2*k+1] = comp(lazy[2*k+1], lazy[k]);
data[k] = reflect(k);
lazy[k] = Oe;
}
}
inline Monoid reflect(int k) {
return lazy[k] == Oe? data[k]:homo(data[k],lazy[k]);
}
inline void recalc(int k) {
while(k>>=1) data[k] = op(reflect(2*k), reflect(2*k+1));
}
inline void thrust(int k) {
for(int i=height;i>0;i--) propagate(k>>i);
}
void update(int a, int b, const OperatorMonoid &x) {
thrust(a+=sz);
thrust(b+=sz-1);
for(int l=a,r=b+1;l<r;l>>=1,r>>=1) {
if(l&1) lazy[l] = comp(lazy[l],x),++l;
if(r&1) --r, lazy[r] = comp(lazy[r],x);
}
recalc(a);
recalc(b);
}
Monoid query(int a, int b) {
thrust(a+=sz);
thrust(b+=sz-1);
Monoid L = e, R = e;
for(int l=a, r=b+1;l<r;l>>= 1,r>>=1) {
if(l&1) L = op(L,reflect(l++));
if(r&1) R = op(reflect(--r),R);
}
return op(L,R);
}
Monoid operator[](const int &k) {
return query(k,k+1);
}
};
struct edge{
int to,id;
ll dist;
edge(int to,ll dist=1,int id=1):to(to),id(id),dist(dist){};
};
class CentroidDecomposition{
public:
int N;
vvec<edge> g;
vec<int> size;
vec<int> used;
CentroidDecomposition(int N,vvec<edge> tree): N(N),g(tree){
size = used = vec<int>(N,0);
}
int calc_size(int cur,int par){
int c = 1;
for(auto& x:g[cur]){
if(x.to==par || used[x.to]) continue;
c += calc_size(x.to,cur);
}
return size[cur] = c;
}
//tは連結成分の大きさ
//cur以下のうち、削除して残る最大の部分木の大きさを返す
Pa<int,int> search_centroid(int cur,int par,int cmp_size){
Pa<int,int> res = {1e9,-1};
int s = 1,ma = 0;
for(auto& x:g[cur]){
if(x.to==par || used[x.to]) continue;
res = min(res,search_centroid(x.to,cur,cmp_size));
ma = max(ma,size[x.to]);
s += size[x.to];
}
//子と親の部分木の大きい方
ma = max(ma,cmp_size-s);
res = min(res,{ma,cur});
return res;
}
void dfs(int cur,int par,ll d,vec<ll>& dlist){
dlist.push_back(d);
for(auto& e:g[cur]) if(e.to!=par && !used[e.to]){
dfs(e.to,cur,d+e.dist,dlist);
}
}
int build(int v){
calc_size(v,-1);
int centroid = search_centroid(v,-1,size[v]).second;
used[centroid] = true;
return centroid;
}
void disable(int v){used[v] = true;}
bool is_alive(int v){return !used[v];}
};
int main(){
cin.tie(0);
ios::sync_with_stdio(false);
int N,M;
cin >> N >> M;
vvec<edge> g(N);
for(int i=0;i<N-1;i++){
int a,b;
cin >> a >> b;
a--; b--;
g[a].push_back(b);
g[b].push_back(a);
}
auto op = [](ll a,ll b){return max(a,b);};
auto func = [](ll a,ll b){return a+b;};
auto comp = func;
LazySegmentTree<ll,ll,decltype(op),decltype(func),decltype(comp)>
seg(N,op,func,comp,-1,0);
struct query{
int id,x,y;
ll z;
bool operator<(const query& R)const{
return id<R.id;
}
};
vvec<query> Q(N);
for(int i=0;i<M;i++){
int x,y,z;
cin >> x >> y >> z;
x--;
Q[x].push_back({i,x,y,z});
}
vec<ll> ans(M);
CentroidDecomposition CD(N,g);
vec<int> dep(N);
queue<int> que;
que.push(0);
while(!que.empty()){
int c = CD.build(CD.build(que.front())); que.pop();
vec<query> now;
int len = 0;
dep[c] = 0;
for(auto& q:Q[c]) now.push_back(q);
auto dfs = [&](auto&& self,int cur,int par,int d)->void{
dep[cur] = d;
len = max(len,d);
for(auto& q:Q[cur]) now.push_back(q);
for(auto& e:g[cur]) if(CD.is_alive(e.to) && e.to!=par){
self(self,e.to,cur,d+1);
}
};
for(auto& x:g[c]) if(CD.is_alive(x.to)) dfs(dfs,x.to,c,1);
sort(now.begin(),now.end());
for(auto& q:now){
ans[q.id] += seg.query(dep[q.x],dep[q.x]+1);
if(dep[q.x]<=q.y) seg.update(0,min(len,q.y-dep[q.x])+1,q.z);
}
now.clear();
for(auto& e:g[c]) if(CD.is_alive(e.to)){
int len2 = 1;
auto dfs = [&](auto&& self,int cur,int par,int d)->void{
dep[cur] = d;
len2 = max(len2,d);
for(auto& q:Q[cur]) now.push_back(q);
for(auto& e:g[cur]) if(CD.is_alive(e.to) && e.to!=par){
self(self,e.to,cur,d+1);
}
};
dfs(dfs,e.to,c,1);
seg.renew(len2);
sort(now.begin(),now.end());
for(auto& q:now){
ans[q.id] -= seg.query(dep[q.x],dep[q.x]+1);
if(dep[q.x]<=q.y) seg.update(0,min(len2,q.y-dep[q.x])+1,q.z);
}
que.push(e.to);
now.clear();
}
seg.renew(len);
}
for(auto& x:ans) cout << x << "\n";
}