結果

問題 No.1038 TreeAddQuery
ユーザー tko919tko919
提出日時 2022-10-19 23:03:41
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,306 ms / 4,000 ms
コード長 12,553 bytes
コンパイル時間 3,124 ms
コンパイル使用メモリ 234,060 KB
実行使用メモリ 108,868 KB
最終ジャッジ日時 2023-09-12 10:36:13
合計ジャッジ時間 23,918 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,384 KB
testcase_01 AC 2 ms
4,384 KB
testcase_02 AC 1 ms
4,384 KB
testcase_03 AC 10 ms
4,832 KB
testcase_04 AC 11 ms
4,596 KB
testcase_05 AC 10 ms
4,876 KB
testcase_06 AC 9 ms
4,592 KB
testcase_07 AC 12 ms
4,664 KB
testcase_08 AC 766 ms
66,712 KB
testcase_09 AC 848 ms
67,824 KB
testcase_10 AC 886 ms
68,464 KB
testcase_11 AC 904 ms
68,356 KB
testcase_12 AC 902 ms
68,632 KB
testcase_13 AC 1,306 ms
108,840 KB
testcase_14 AC 1,080 ms
76,284 KB
testcase_15 AC 1,056 ms
74,796 KB
testcase_16 AC 994 ms
71,624 KB
testcase_17 AC 1,033 ms
71,232 KB
testcase_18 AC 538 ms
64,292 KB
testcase_19 AC 543 ms
64,856 KB
testcase_20 AC 491 ms
64,960 KB
testcase_21 AC 459 ms
64,904 KB
testcase_22 AC 520 ms
64,520 KB
testcase_23 AC 528 ms
64,644 KB
testcase_24 AC 617 ms
64,448 KB
testcase_25 AC 1,277 ms
108,868 KB
testcase_26 AC 938 ms
86,312 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 1 "library/Template/template.hpp"
#include <bits/stdc++.h>
using namespace std;

#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define ALL(v) (v).begin(),(v).end()
using ll=long long int;
const int inf = 0x3fffffff;
const ll INF = 0x1fffffffffffffff;
template<typename T>inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T>inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
#line 2 "library/Utility/fastio.hpp"
#include <unistd.h>

class FastIO{
    static constexpr int L=1<<16;
    char rdbuf[L];
    int rdLeft=0,rdRight=0;
    inline void reload(){
        int len=rdRight-rdLeft;
        memmove(rdbuf,rdbuf+rdLeft,len);
        rdLeft=0,rdRight=len;
        rdRight+=fread(rdbuf+len,1,L-len,stdin);
    }
    inline bool skip(){
        for(;;){
            while(rdLeft!=rdRight and rdbuf[rdLeft]<=' ')rdLeft++;
            if(rdLeft==rdRight){
                reload();
                if(rdLeft==rdRight)return false;
            }
            else break;
        }
        return true;
    }
    template<typename T,enable_if_t<is_integral<T>::value,int> =0>inline bool _read(T& x){
        if(!skip())return false;
        if(rdLeft+20>=rdRight)reload();
        bool neg=false;
        if(rdbuf[rdLeft]=='-'){
            neg=true;
            rdLeft++;
        }
        x=0;
        while(rdbuf[rdLeft]>='0' and rdLeft<rdRight){
            x=x*10+(neg?-(rdbuf[rdLeft++]^48):(rdbuf[rdLeft++]^48));
        }
        return true;
    }
    template<typename T,enable_if_t<is_floating_point<T>::value,int> =0>inline bool _read(T& x){
        if(!skip())return false;
        if(rdLeft+20>=rdRight)reload();
        bool neg=false;
        if(rdbuf[rdLeft]=='-'){
            neg=true;
            rdLeft++;
        }
        x=0;
        while(rdbuf[rdLeft]>='0' and rdbuf[rdLeft]<='9' and rdLeft<rdRight){
            x=x*10+(rdbuf[rdLeft++]^48);
        }
        if(rdbuf[rdLeft]!='.')return true;
        rdLeft++;
        T base=.1;
        while(rdbuf[rdLeft]>='0' and rdbuf[rdLeft]<='9' and rdLeft<rdRight){
            x+=base*(rdbuf[rdLeft++]^48);
            base*=.1;
        }
        if(neg)x=-x;
        return true;
    }
    inline bool _read(char& x){
        if(!skip())return false;
        if(rdLeft+1>=rdRight)reload();
        x=rdbuf[rdLeft++];
        return true;
    }
    inline bool _read(string& x){
        if(!skip())return false;
        for(;;){
            int pos=rdLeft;
            while(pos<rdRight and rdbuf[pos]>' ')pos++;
            x.append(rdbuf+rdLeft,pos-rdLeft);
            if(rdLeft==pos)break;
            rdLeft=pos;
            if(rdLeft==rdRight)reload();
            else break;
        }
        return true;
    }
    template<typename T>inline bool _read(vector<T>& v){
        for(auto& x:v){
            if(!_read(x))return false;
        }
        return true;
    }

    char wtbuf[L],tmp[50];
    int wtRight=0;
    inline void flush(){
        fwrite(wtbuf,1,wtRight,stdout);
        wtRight=0;
    }
    inline void _write(const char& x){
        if(wtRight>L-32)flush();
        wtbuf[wtRight++]=x;
    }
    inline void _write(const string& x){
        for(auto& c:x)_write(c);
    }
    template<typename T,enable_if_t<is_integral<T>::value,int> =0>inline void _write(T x){
        if(wtRight>L-32)flush();
        if(x==0){
            _write('0');
            return;
        }
        else if(x<0){
            _write('-');
            if (__builtin_expect(x == std::numeric_limits<T>::min(), 0)) {
                switch (sizeof(x)) {
                case 2: _write("32768"); return;
                case 4: _write("2147483648"); return;
                case 8: _write("9223372036854775808"); return;
                }
            }
            x=-x;
        }
        int pos=0;
        while(x!=0){
            tmp[pos++]=char((x%10)|48);
            x/=10;
        }
        rep(i,0,pos)wtbuf[wtRight+i]=tmp[pos-1-i];
        wtRight+=pos;
    }
    template<typename T>inline void _write(const vector<T>& v){
        rep(i,0,v.size()){
            if(i)_write(' ');
            _write(v[i]);
        }
    }
public:
    FastIO(){}
    ~FastIO(){flush();}
    inline void read(){}
    template <typename Head, typename... Tail>inline void read(Head& head,Tail&... tail){
        assert(_read(head));
        read(tail...); 
    }
    template<bool ln=true,bool space=false>inline void write(){if(ln)_write('\n');}
    template <bool ln=true,bool space=false,typename Head, typename... Tail>inline void write(const Head& head,const Tail&... tail){
        if(space)_write(' ');
        _write(head);
        write<ln,true>(tail...); 
    }
};

/**
 * @brief Fast IO
 */
#line 3 "sol.cpp"

#line 2 "library/Graph/centroid.hpp"

class CentroidDecomposition{
    void get(int v,int p){
        sz[v]=1;
        for(auto& to:g[v])if(to!=p and !used[to]){
            get(to,v);
            sz[v]+=sz[to];
        }
    }
    int dfs(int v,int p,int rt){
        for(auto& to:g[v])if(to!=p and !used[to]){
            if(sz[to]>(sz[rt]>>1))return dfs(to,v,rt);
        }
        return v;
    }
public:
    int n;
    vector<vector<int>> g;
    vector<int> sz,used;
    CentroidDecomposition(int n_):n(n_),g(n),sz(n),used(n){}
    void add_edge(int u,int v){
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int find(int rt){
        get(rt,-1);
        int res=dfs(rt,-1,rt);
        used[res]=1;
        return res;
    }
};

/**
 * @brief Centroid Decomposition
 */
#line 2 "library/Graph/hld.hpp"

struct HLD{
    using P=pair<int,int>;
    vector<vector<int>> g; vector<int> sz,in,out,rev,hs,par,dist;
    void dfs(int v,int p){
        par[v]=p; sz[v]=1; dist[v]=dist[p]+1;
        if(!g[v].empty() and g[v][0]==p)swap(g[v][0],g[v].back());
        for(auto& to:g[v])if(to!=p){
           dfs(to,v); sz[v]+=sz[to];
           if(sz[g[v][0]]<sz[to])swap(g[v][0],to);
        }
    }
    void dfs2(int v,int p,int& k){
        in[v]=k++; rev[in[v]]=v;
        for(auto& to:g[v])if(to!=p){
            hs[to]=(g[v][0]==to?hs[v]:to);
            dfs2(to,v,k);
        }
        out[v]=k;
    }
    HLD(int _n):g(_n),sz(_n),in(_n),out(_n),rev(_n),hs(_n),par(_n),dist(_n){}
    void add_edge(int u,int v){
        g[u].emplace_back(v); g[v].emplace_back(u);
    }
    void run(int rt=0){dfs(rt,-1); hs[rt]=rt; int k=0; dfs2(rt,-1,k);}
    int lca(int u,int v){
        for(;;v=par[hs[v]]){
            if(in[u]>in[v])swap(u,v);
            if(hs[u]==hs[v])return u;
        }
    }
    vector<P> get(int u,int p,bool es=0){
        assert(in[p]<=in[u] and out[u]<=out[p]);
        vector<P> res;
        while(hs[u]!=hs[p]){
            res.push_back({in[hs[u]],in[u]+1});
            u=par[hs[u]];
        }
        res.push_back({in[p]+es,in[u]+1});
        return res;
    }
    int jump(int u,int v,int k){
        if(k<0)return -1;
        int g=lca(u,v);
        int d0=dist[u]+dist[v]-dist[g]*2;
        if(d0<k)return -1;
        int st=u;
        if(dist[u]-dist[g]<k)st=v,k=d0-k;
        for(;;){
            int to=hs[st];
            if(in[st]-k>=in[to])return rev[in[st]-k];
            k-=in[st]-in[to]+1; st=par[to];
        }
    }
};

/**
 * @brief Heavy Light Decomposition
 */
#line 6 "sol.cpp"

struct ContourQuery{
    using P=pair<int,int>;
    using T=pair<int,P>;
    ContourQuery(int _n=0):n(_n),m(_n),cd(_n),
        hld(_n),tree(_n*3),depth(_n*3),
        base(_n*3),parent(_n*3,-1),SZ(_n*3),width(_n*3,1),seg(_n*3){}
    void add_edge(int u,int v){
        cd.add_edge(u,v);
        hld.add_edge(u,v);
    }
    vector<int> run(){
        hld.run();
        root=rec(0);
        depth[0]=0;
        dfs(0,-1);
        rep(v,0,m)if(v!=root){
            seg[v]=width[v];
        }
        return seg;
    }
    vector<P> point(int v){
        vector<P> ret;
        int cur=v;
        while(cur!=root){
            int D=depth[v]+depth[base[cur]]-2*depth[hld.lca(v,base[cur])];
            ret.push_back({cur,D});
            cur=parent[cur];
        }
        return ret;
    }
    vector<T> range(int v,int L,int R){
        vector<T> ret;
        if(L<=0 and 0<R)ret.push_back({v,{0,1}});
        int cur=parent[v],pre=v;
        while(pre!=root){
            int bro=-1;
            for(auto& to:tree[cur])if(to!=parent[cur] and to!=pre){
                bro=to;
                break;
            }
            if(bro!=-1){
                int D=depth[v]+depth[base[bro]]-2*depth[hld.lca(v,base[bro])];
                ret.push_back({bro,{clamp(L-D,0,seg[bro]),clamp(R-D,0,seg[bro])}});
            }
            pre=cur;
            cur=parent[cur];
        }
        return ret;
    }
private:
    int n,m,root;
    CentroidDecomposition cd;
    HLD hld;
    vector<vector<int>> tree;
    vector<int> depth,base,parent,SZ,width,seg;
    int rec(int rt){
        int cen=cd.find(rt);
        SZ[cen]=1;
        queue<P> que;
        auto cmp=[&](int u,int v){return SZ[u]>SZ[v];};
        priority_queue<int,vector<int>,decltype(cmp)> pq{cmp};
        pq.push(cen);
        depth[cen]=0;
        base[cen]=cen;
        for(auto& to:cd.g[cen])if(!cd.used[to]){
            int v=rec(to);
            que.push({to,cen});
            depth[to]=1;
            while(!que.empty()){
                auto [cur,par]=que.front();
                que.pop();
                width[v]=depth[cur]+1;
                for(auto& nxt:cd.g[cur])if(nxt!=par and !cd.used[nxt]){
                    depth[nxt]=depth[cur]+1;
                    que.push({nxt,cur});
                }
            }
            pq.push(v);
            base[v]=cen;
        }
        cd.used[cen]=0;
        if(pq.size()>1){
            for(;;){
                int v1=pq.top();
                pq.pop();
                int v2=pq.top();
                pq.pop();
                int extra=m++;
                tree[extra].push_back(v1);
                tree[extra].push_back(v2);
                tree[v1].push_back(extra);
                tree[v2].push_back(extra);
                SZ[extra]=SZ[v1]+SZ[v2];
                parent[v1]=parent[v2]=extra;
                if(pq.empty()){
                    return extra;
                }
                pq.push(extra);
                base[extra]=cen;
                width[extra]=max(width[v1],width[v2]);
            }
        }
        else{
            int extra=m++;
            tree[extra].push_back(cen);
            tree[cen].push_back(extra);
            SZ[extra]=1;
            parent[cen]=extra;
            return extra;
        }
    }
    void dfs(int v,int p){
        for(auto& to:cd.g[v])if(to!=p){
            depth[to]=depth[v]+1;
            dfs(to,v);
        }
    }
};

#line 2 "library/DataStructure/dualsegtree.hpp"

template<typename M,M (*f)(M,M),M (*m1)()>class DualSegmentTree{
    int sz,height;
    vector<M> data;
    void down(int k){
        data[k*2]=f(data[k*2],data[k]);
        data[k*2+1]=f(data[k*2+1],data[k]);
        data[k]=m1();
    }
public:
    DualSegmentTree(){}
    DualSegmentTree(int n){
        sz=1,height=0;
        while(sz<n)sz<<=1,height++;
        data.assign(2*sz,m1());
    }
    void run(vector<M>& v){
        for(int i=0;i<(int)v.size();i++)data[i+sz]=v[i];
    }
    void update(int a,int b,M x){
        if(a>=b)return;
        a+=sz,b+=sz;
        for(int i=height;i;i--){
            if(((a>>i)<<i)!=a)down(a>>i);
            if(((b>>i)<<i)!=b)down((b-1)>>i);
        }
        for(;a<b;a>>=1,b>>=1){
            if(a&1)data[a]=f(data[a],x),a++;
            if(b&1)--b,data[b]=f(data[b],x);
        }
    }
    M query(int k){
        k+=sz;
        for(int i=height;i;i--){
            if(((k>>i)<<i)!=k)down(k>>i);
        }
        M ret=data[k];
        while(k>>=1)ret=f(ret,data[k]);
        return ret;
    }
};

/**
 * @brief Dual Segment Tree
 */
#line 127 "sol.cpp"

ll f(ll a,ll b){return a+b;}
ll m1(){return 0;}

FastIO io;
int main(){
    int n,q;
    io.read(n,q);
    ContourQuery buf(n);
    rep(_,0,n-1){
        int a,b;
        io.read(a,b);
        a--; b--;
        buf.add_edge(a,b);
    }  
    auto len=buf.run();
    vector<DualSegmentTree<ll,f,m1>> seg(len.size());
    rep(i,0,len.size())seg[i]=DualSegmentTree<ll,f,m1>(len[i]);
    while(q--){
        int x,y,z;
        io.read(x,y,z);
        x--;
        ll ret=0; 
        for(auto& [i,v]:buf.point(x)){
            ret+=seg[i].query(v);
        }
        io.write(ret);
        for(auto& [i,LR]:buf.range(x,0,y+1)){
            auto [L,R]=LR;
            seg[i].update(L,R,z);
        }
    }
    return 0;
}
0