結果

問題 No.1038 TreeAddQuery
ユーザー chocoruskchocorusk
提出日時 2020-04-25 00:12:04
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2,812 ms / 4,000 ms
コード長 6,726 bytes
コンパイル時間 2,544 ms
コンパイル使用メモリ 163,988 KB
実行使用メモリ 106,292 KB
最終ジャッジ日時 2024-11-25 04:46:49
合計ジャッジ時間 35,080 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
7,752 KB
testcase_01 AC 4 ms
7,392 KB
testcase_02 AC 3 ms
7,124 KB
testcase_03 AC 14 ms
8,524 KB
testcase_04 AC 17 ms
8,624 KB
testcase_05 AC 15 ms
9,288 KB
testcase_06 AC 13 ms
8,524 KB
testcase_07 AC 17 ms
8,704 KB
testcase_08 AC 1,579 ms
72,020 KB
testcase_09 AC 1,879 ms
75,676 KB
testcase_10 AC 1,893 ms
75,764 KB
testcase_11 AC 1,879 ms
75,752 KB
testcase_12 AC 2,001 ms
76,404 KB
testcase_13 AC 2,812 ms
106,292 KB
testcase_14 AC 2,517 ms
86,976 KB
testcase_15 AC 2,448 ms
83,660 KB
testcase_16 AC 2,359 ms
82,108 KB
testcase_17 AC 2,258 ms
80,936 KB
testcase_18 AC 335 ms
56,484 KB
testcase_19 AC 414 ms
57,604 KB
testcase_20 AC 392 ms
57,744 KB
testcase_21 AC 501 ms
59,588 KB
testcase_22 AC 748 ms
63,576 KB
testcase_23 AC 895 ms
64,092 KB
testcase_24 AC 1,432 ms
72,332 KB
testcase_25 AC 2,733 ms
106,176 KB
testcase_26 AC 1,465 ms
81,664 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 MAX_V = 100010;  // ツリーのサイズのありうる最大値

int N;  // ツリーのサイズ
vector<vector<int>> tree;  // ツリーを隣接リスト形式のグラフ構造で表したもの

int sizeSubtree[MAX_V];  // sizeSubtree[v] := v を根とする部分ツリーのサイズ (分割統治の毎ステップごとに再利用)
bool isRemoved[MAX_V];  // isRemoved[v] := v が既に取り除かれたかどうか
int whoIsParent[MAX_V];  // whoIsParent[v] := ツリーDP時に v の親が誰だったか

// メイン処理
vector<int> centroids;
void FindCentroidRecursive(int v, int size, int p = -1) {
    sizeSubtree[v] = 1;
    whoIsParent[v] = p;
    bool isCentroid = true;
    for (auto ch : tree[v]) {
        if (ch == p) continue;
        if (isRemoved[ch]) continue;
        FindCentroidRecursive(ch, size, v);
        if (sizeSubtree[ch] > size / 2) isCentroid = false;
        sizeSubtree[v] += sizeSubtree[ch];
    }
    if (size - sizeSubtree[v] > size / 2) isCentroid = false;
    if (isCentroid) centroids.push_back(v);
}

// 初期化
void Init() {
    for (int i = 0; i < MAX_V; ++i) {
        isRemoved[i] = false;
    }
}

// first: 重心, second: (重心の子ノード, 子部分木のサイズ) からなるベクトル
pair<int, vector<pair<int,int> > > FindCentroid(int root, int size) {
    vector<pair<int, int> > subtrees;
    centroids.clear();
    FindCentroidRecursive(root, size);
    int center = centroids[0];
    for (auto ch : tree[center]) {
        if (isRemoved[ch]) continue;
        if (ch == whoIsParent[center]) {
            subtrees.push_back(make_pair(ch, size - sizeSubtree[center]));
        }
        else {
            subtrees.push_back(make_pair(ch, sizeSubtree[ch]));
        }
    }
    return make_pair(center, subtrees);
}
int par[100010];
vector<P> vd[100010];
int dist[100010];
void dfs(int v, int p, int cent){
    whoIsParent[v] = p;
    vd[cent].push_back({v, dist[v]});
    for(auto ch:tree[v]){
        if (ch == p) continue;
        if (isRemoved[ch]) continue;
        dist[ch]=dist[v]+1;
        dfs(ch, v, cent);
    }
}
map<P, int> ind;
int id;
vector<vector<P>> vdc;
int pc[100010];
void dfs1(int v, int p, int cent){
	vdc[cent].push_back({v, dist[v]});
	for(auto ch:tree[v]){
        if (ch == p) continue;
        if (isRemoved[ch]) continue;
        dist[ch]=dist[v]+1;
        dfs1(ch, v, cent);
    }
}
void myon(int root, int size, int p=-1){
    if(size<=1){
        par[root]=p;
		if(p!=-1) pc[root]=root;
		else pc[root]=-1;
        vd[root].push_back({root, 0});
        return;
    }
    auto pr=FindCentroid(root, size);
    int cent=pr.first;
	if(p!=-1) pc[cent]=root;
	else pc[cent]=-1;
    dist[cent]=0;
    dfs(cent, -1, cent);
    par[cent]=p;
    isRemoved[cent]=1;
    for(auto prr:pr.second){
        if(!isRemoved[prr.first]){
			dist[prr.first]=0;
			ind[{cent, prr.first}]=id;
			vector<P> nw;
			vdc.push_back(nw);
			dfs1(prr.first, -1, id);
			id++;
			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;
	tree.resize(n);
	for(int i=0; i<n-1; i++){
		int a, b; scanf("%d %d", &a, &b); a--; b--;
		tree[a].push_back(b);
		tree[b].push_back(a);
	}
	myon(0, n);
	int mx[100010]={}, mxc[200020]={};
	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(id);
	for(int i=0; i<n; i++){
		seg[i].init(mx[i]);
	}
	for(int i=0; i<id; 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(tree);
	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);

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

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