結果

問題 No.1038 TreeAddQuery
ユーザー IKyoproIKyopro
提出日時 2020-04-24 23:06:05
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 3,496 bytes
コンパイル時間 3,027 ms
コンパイル使用メモリ 217,656 KB
実行使用メモリ 13,896 KB
最終ジャッジ日時 2024-04-23 04:10:17
合計ジャッジ時間 9,449 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
13,756 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 130 ms
6,944 KB
testcase_04 AC 145 ms
6,944 KB
testcase_05 AC 117 ms
6,944 KB
testcase_06 AC 94 ms
6,940 KB
testcase_07 AC 135 ms
6,944 KB
testcase_08 TLE -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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>>;



struct edge{
    int to,id;
    ll dist;
    edge(int to,ll dist=1,int id=1):to(to),id(id),dist(dist){};
};

template<typename T>
struct SparseTable {
    vector<vector<T>> st;
    vector<int> lookup;

    SparseTable(){}
    SparseTable(const vector<T> &v) {
        int b = 0;
        while((1<<b)<=v.size()) ++b;
            st.assign(b,vector<T>(1<<b));
            for(int i=0;i<v.size();i++) {
                st[0][i] = v[i];
            }
            for(int i=1;i<b;i++) {
            for(int j=0;j+(1<<i)<=(1<<b);j++) {
                st[i][j] = min(st[i-1][j],st[i-1][j+(1<<(i-1))]);
            }
        }
        lookup.resize(v.size()+1);
        for(int i=2;i<lookup.size();i++) {
            lookup[i] = lookup[i>>1]+1;
        }
    }

    inline T query(int l,int r) {
        int b = lookup[r-l];
        return min(st[b][l],st[b][r-(1<<b)]);
    }
};

class LCA{
private:
    vec<int> idx,dep,vs;
    vec<int> dist;
    vec<Pa<int,int>> init;
    
    SparseTable<Pa<int,int>> st;

    vvec<edge> g;
    
    int pos;
    
    void dfs(int cur,int par,int d){
        idx[cur] = pos;
        vs[pos] = cur;
        dep[pos++] = d;
        dist[cur] = d;
        for(auto& e:g[cur]) if(e.to!=par){
            dfs(e.to,cur,d+1);
            vs[pos] = cur;
            dep[pos++] = d;
        }
    }

public:
    LCA(){};
    LCA(int N,int root,vvec<edge> g):idx(N),dep(2*N),vs(2*N),init(2*N),g(g){
        pos = 0;
        dist = vec<int>(N);
        dfs(root,-1,0);
        for(int i=0;i<2*N;i++){
            init[i] = {dep[i],vs[i]};
        }
        st = SparseTable<Pa<int,int>>(init);
    }

    int lca(int u,int v){
        if(idx[u]>idx[v]) swap(u,v);
        return st.query(idx[u],idx[v]+1).second;
    }
    int vid(int v){return idx[v];}
    int idv(int i){return vs[i];}
    int depth(int i){return dep[i];}
    int d(int i){return dist[i];}
};

constexpr int si = 512;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,Q;
    cin >> N >> Q;
    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);
    }
    LCA lca(N,0,g);
    struct query{
        int x,y;
        ll z;
    };
    vec<query> q(Q);
    for(int i=0;i<Q;i++){
        int x,y,z;
        cin >> x >> y >> z;
        x--;
        q[i] = {x,y,z};
    }
    vec<ll> ans(N);

    auto dist = [&](int a,int b){
        return lca.d(a)+lca.d(b)-2*lca.d(lca.lca(a,b));
    };

    for(int _=0;_<Q;_+=si){
        int l = _,r = min(Q,_+si);
        //cerr << l << " " << r << "\n";
        //query answer
        for(int i=l;i<r;i++){
            ll now = ans[q[i].x];
           // cerr << "q : " << i << "\n";
            for(int j=l;j<i;j++){
                int d = dist(q[i].x,q[j].x);
             //   cerr << q[i].x << " " << q[j].x << " " << d << "\n";
                if(d<=q[j].y){
                    now += q[j].z;
                }
            }
            cout << now << "\n";
        }
        //prepare next
        //cerr << "in\n";
        for(int i=0;i<N;i++){
            for(int j=l;j<r;j++){
                int d = dist(i,q[j].x);
                if(d<=q[j].y) ans[i] += q[j].z;
            }
        }
        //cerr << "out\n";
    }
}
0