結果

問題 No.1038 TreeAddQuery
ユーザー chocoruskchocorusk
提出日時 2020-04-25 00:02:55
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 3,549 ms / 4,000 ms
コード長 6,815 bytes
コンパイル時間 2,190 ms
コンパイル使用メモリ 161,736 KB
実行使用メモリ 111,616 KB
最終ジャッジ日時 2024-04-23 04:25:46
合計ジャッジ時間 46,115 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 3 ms
6,944 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 21 ms
7,800 KB
testcase_04 AC 25 ms
8,012 KB
testcase_05 AC 21 ms
7,888 KB
testcase_06 AC 21 ms
7,508 KB
testcase_07 AC 26 ms
7,884 KB
testcase_08 AC 2,141 ms
82,280 KB
testcase_09 AC 2,512 ms
86,936 KB
testcase_10 AC 2,590 ms
87,632 KB
testcase_11 AC 2,609 ms
87,796 KB
testcase_12 AC 2,715 ms
88,772 KB
testcase_13 AC 3,549 ms
111,588 KB
testcase_14 AC 3,278 ms
100,256 KB
testcase_15 AC 3,141 ms
97,672 KB
testcase_16 AC 3,050 ms
96,684 KB
testcase_17 AC 2,931 ms
95,228 KB
testcase_18 AC 634 ms
55,492 KB
testcase_19 AC 681 ms
58,608 KB
testcase_20 AC 689 ms
58,868 KB
testcase_21 AC 782 ms
62,192 KB
testcase_22 AC 1,124 ms
69,212 KB
testcase_23 AC 1,285 ms
70,820 KB
testcase_24 AC 2,027 ms
84,376 KB
testcase_25 AC 3,488 ms
111,616 KB
testcase_26 AC 1,943 ms
83,676 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; cin>>a>>b; a--; b--;
		tree[a].push_back(b);
		tree[b].push_back(a);
	}
	myon(0, n);
	for(int i=0; i<n; i++){
		sort(vd[i].begin(), vd[i].end());
	}
	for(int i=0; i<id; i++) sort(vd[i].begin(), vd[i].end());
	vector<RangeAddPointGet<ll>> seg(n), segc(id);
	for(int i=0; i<n; i++){
		seg[i].init(vd[i].size());
	}
	for(int i=0; i<id; i++){
		sort(vdc[i].begin(), vdc[i].end());
		segc[i].init(vdc[i].size());
	}
	LCA lca(tree);
	lca.build();
	while(q--){
		int x, y; ll z;
		cin>>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);
			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);
			}
		}
		printf("%lld\n", ans);
		x1=x;
		while(x1!=-1){
			int d1=y-lca.dist(x, x1);
			if(d1<0) d1=-1;
			if(d1>=(int)vd[x1].size()) d1=(int)vd[x1].size()-1;
			seg[x1].add(0, d1+1, z);
			int p=pc[x1];
			x1=par[x1];
			if(x1!=-1){
				p=ind[{x1, p}];
				d1=y-lca.dist(x, x1)-1;
				if(d1<0) d1=-1;
				if(d1>=(int)vdc[p].size()) d1=(int)vdc[p].size()-1;
				segc[p].add(0, d1+1, -z);
			}
		}
	}
	return 0;
}
0