結果

問題 No.1038 TreeAddQuery
ユーザー chocoruskchocorusk
提出日時 2020-05-01 05:08:20
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,996 ms / 4,000 ms
コード長 5,309 bytes
コンパイル時間 2,107 ms
コンパイル使用メモリ 154,896 KB
実行使用メモリ 104,204 KB
最終ジャッジ日時 2024-12-22 21:05:21
合計ジャッジ時間 28,815 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
9,164 KB
testcase_01 AC 5 ms
9,344 KB
testcase_02 AC 5 ms
9,216 KB
testcase_03 AC 15 ms
10,368 KB
testcase_04 AC 17 ms
10,240 KB
testcase_05 AC 16 ms
10,624 KB
testcase_06 AC 14 ms
10,240 KB
testcase_07 AC 18 ms
10,496 KB
testcase_08 AC 1,129 ms
65,860 KB
testcase_09 AC 1,334 ms
69,024 KB
testcase_10 AC 1,373 ms
69,436 KB
testcase_11 AC 1,336 ms
69,532 KB
testcase_12 AC 1,395 ms
70,512 KB
testcase_13 AC 1,996 ms
104,204 KB
testcase_14 AC 1,835 ms
81,712 KB
testcase_15 AC 1,772 ms
78,052 KB
testcase_16 AC 1,701 ms
76,368 KB
testcase_17 AC 1,692 ms
75,200 KB
testcase_18 AC 252 ms
49,720 KB
testcase_19 AC 328 ms
51,216 KB
testcase_20 AC 313 ms
51,552 KB
testcase_21 AC 408 ms
53,372 KB
testcase_22 AC 568 ms
57,320 KB
testcase_23 AC 626 ms
57,832 KB
testcase_24 AC 1,007 ms
65,924 KB
testcase_25 AC 1,955 ms
104,100 KB
testcase_26 AC 1,080 ms
77,548 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
const int MAXN=100010;
vector<vector<int>> g;
int sz[MAXN], par[MAXN];
bool isremoved[MAXN];
vector<int> centroids;

int dist[MAXN];

void findcentroid_rec(int x, int p, int size, vector<P> &v){
	sz[x]=1, par[x]=p;

	v.push_back({x, dist[x]});

	bool cent=1;
	for(auto y:g[x]){
		if(y==p) continue;
		if(isremoved[y]) continue;
		dist[y]=dist[x]+1;
		findcentroid_rec(y, x, size, v);
		if(sz[y]>size/2) cent=0;
		sz[x]+=sz[y];
	}
	if(size-sz[x]>size/2) cent=0;
	if(cent) centroids.push_back(x);
}
pair<int, vector<pair<int, int>>> findcentroid(int root, int size, vector<P> &v){
	vector<pair<int, int>> subtrees;
	centroids.clear();
	findcentroid_rec(root, -1, size, v);
	int cent=centroids[0];
	for(auto y:g[cent]){
		if(isremoved[y]) continue;
		if(y==par[cent]){
			subtrees.push_back({y, size-sz[cent]});
		}else{
			subtrees.push_back({y, sz[y]});
		}
	}
	return make_pair(cent, subtrees);
}
int parc[MAXN];
vector<P> vd[MAXN], vdc[MAXN];
void dfs(int x, int p, int cent){
    vd[cent].push_back({x, dist[x]});
    for(auto y:g[x]){
        if(y==p) continue;
		if(isremoved[y]) continue;
        dist[y]=dist[x]+1;
        dfs(y, x, cent);
    }
}
void myon(int root, int size, int p=-1){
    if(size<=1){
        parc[root]=p;
		vdc[root].push_back({root, 0});
        vd[root].push_back({root, 0});
        return;
    }
	dist[root]=0;
	vector<P> v;
    auto pr=findcentroid(root, size, v);
    int cent=pr.first;
	swap(vdc[cent], v);
    dist[cent]=0;
    dfs(cent, -1, cent);
    parc[cent]=p;
    isremoved[cent]=1;
    for(auto prr:pr.second){
        if(!isremoved[prr.first]){
			myon(prr.first, prr.second, cent);
		}
    }
}
struct LCA{
    vector<vector<int>> g;
    vector<int> d;
    vector<vector<int>> p;
    int log;
    int n;
    LCA(const vector<vector<int>> &g):g(g), d(g.size()), n(g.size()){
        log=0;
        while(1<<log<=n) log++;
        p.resize(log, vector<int>(n));
    }
    void dfs(int x, int prev){
        for(auto y:g[x]){
            if(y==prev) continue;
            d[y]=d[x]+1;
            p[0][y]=x;
            dfs(y, x);
        }
    }
    void build(){
        dfs(0, -1);
        for(int i=1; i<log; i++){
            for(int j=0; j<n; j++){
                p[i][j]=p[i-1][p[i-1][j]];
            }
        }
    }
    int lca(int a, int b){
        if(d[a]>d[b]) swap(a, b);
        int dd=d[b]-d[a], i=0;
        int a1=a, b1=b;
        while(dd){
            if(dd&1) b1=p[i][b1];
            dd>>=1;
            i++;
        }
        if(a1==b1) return a1;
        for(int j=log-1; j>=0; j--){
            if(p[j][a1]!=p[j][b1]){
                a1=p[j][a1], b1=p[j][b1];
            }
        }
        return p[0][a1];
    }
    int dist(int a, int b){
        return d[a]+d[b]-2*d[lca(a, b)];
    }
};
template<typename T>
struct BIT{
    vector<T> bit;
    int size;
	BIT(){}
    BIT(int n):size(n), bit(n+1, 0){}
	void init(int n){
		size=n; bit.resize(n+1);
	}
    T sum(int i){ //[0, i)
        T s=0;
        while(i>0){
            s+=bit[i];
            i-=(i&(-i));
        }
        return s;
    }
    T sum(int l, int r){ //[l, r)
        return sum(r)-sum(l);
    }
    void add(int i, T x){
		i++;
        while(i<=size){
            bit[i]+=x;
            i+=(i&(-i));
        }
    }
};
template<typename T>
struct RangeAddPointGet{
	BIT<T> bit;
	RangeAddPointGet(){}
	RangeAddPointGet(int n):bit(n){}
	void init(int n){
		bit.init(n);
	}
	void add(int l, int r, T x){
		bit.add(l, x);
		bit.add(r, -x);	
	}
	T get(int i){
		return bit.sum(i+1);
	}
};
int main()
{
	int n, q; cin>>n>>q;
	g.resize(n);
	for(int i=0; i<n-1; i++){
		int a, b; scanf("%d %d", &a, &b); a--; b--;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	myon(0, n);
	int mx[MAXN]={}, mxc[MAXN]={};
	for(int i=0; i<n; i++){
		sort(vd[i].begin(), vd[i].end());
		for(auto x:vd[i]) mx[i]=max(mx[i], x.second+1);
	}
	vector<RangeAddPointGet<ll>> seg(n), segc(n);
	for(int i=0; i<n; i++){
		seg[i].init(mx[i]);
	}
	for(int i=0; i<n; i++){
		sort(vdc[i].begin(), vdc[i].end());
		for(auto x:vdc[i]) mxc[i]=max(mxc[i], x.second+1);
		segc[i].init(mxc[i]);
	}
	LCA lca(g);
	lca.build();
	while(q--){
		int x, y; ll z;
		scanf("%d %d %lld", &x, &y, &z);
		x--;
		int x1=x;
		ll ans=0;
		while(x1!=-1){
			int t=lower_bound(vd[x1].begin(), vd[x1].end(), P(x, 0))-vd[x1].begin();
			int d1=vd[x1][t].second;
			ans+=seg[x1].get(d1);

			d1=y-lca.dist(x, x1);
			if(d1<0) d1=-1;
			seg[x1].add(0, min(d1+1, mx[x1]), z);

			if(parc[x1]!=-1){
				t=lower_bound(vdc[x1].begin(), vdc[x1].end(), P(x, 0))-vdc[x1].begin();
				d1=vdc[x1][t].second;
				ans+=segc[x1].get(d1);

				d1=y-lca.dist(x, parc[x1])-1;
				if(d1<0) d1=-1;
				segc[x1].add(0, min(d1+1, mxc[x1]), -z);
			}
			x1=parc[x1];
		}
		printf("%lld\n", ans);
	}
	return 0;
}
0