#960487 (C++17) No.2676 A Tourist

提出ソース
結果

問題	No.2676 A Tourist
コンテスト
ユーザー	👑 potato167
提出日時	2024-03-15 22:24:07
言語	C++17 (gcc 13.3.0 + boost 1.87.0)
結果	WA
実行時間	-
コード長	12,958 bytes
コンパイル時間	3,144 ms
コンパイル使用メモリ	228,396 KB
最終ジャッジ日時	2025-02-20 05:29:15
ジャッジサーバーID （参考情報）	judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 1 -- * 1
other	AC * 5 WA * 5 TLE * 1 -- * 20
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
using namespace std;
using std::cout;
using std::cin;
using std::endl;
using ll=long long;
using ld=long double;
const ll ILL=2167167167167167167;
const int INF=2100000000;
const int mod=998244353;
#define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++)
#define all(p) p.begin(),p.end()
template<class T> using _pq = priority_queue<T, vector<T>, greater<T>>;
template<class T> ll LB(vector<T> &v,T a){return lower_bound(v.begin(),v.end(),a)-v.begin();}
template<class T> ll UB(vector<T> &v,T a){return upper_bound(v.begin(),v.end(),a)-v.begin();}
template<class T> bool chmin(T &a,T b){if(a>b){a=b;return 1;}else return 0;}
template<class T> bool chmax(T &a,T b){if(a<b){a=b;return 1;}else return 0;}
template<class T> void So(vector<T> &v) {sort(v.begin(),v.end());}
template<class T> void Sore(vector<T> &v) {sort(v.begin(),v.end(),[](T x,T y){return x>y;});}
void yneos(bool a,bool upp=0){if(a) cout<<(upp?"YES\n":"Yes\n"); else cout<<(upp?"NO\n":"No\n");}
template<class T> void vec_out(vector<T> &p,int ty=0){
if(ty==2){cout<<'{';for(int i=0;i<(int)p.size();i++){if(i){cout<<",";}cout<<'"'<<p[i]<<'"';}cout<<"}\n";}
else{if(ty==1){cout<<p.size()<<"\n";}for(int i=0;i<(int)(p.size());i++){if(i) cout<<" ";cout<<p[i];}cout<<"\n";}}
template<class T> T vec_min(vector<T> &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmin(ans,x);return ans;}
template<class T> T vec_max(vector<T> &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmax(ans,x);return ans;}
template<class T> T vec_sum(vector<T> &a){T ans=T(0);for(auto &x:a) ans+=x;return ans;}
int pop_count(long long a){int res=0;while(a){res+=(a&1),a>>=1;}return res;}
/*

#include<vector>
#include<cassert>
#include<math.h>

*/

namespace po167{
struct LCA{
    std::vector<int> deep;
    std::vector<std::vector<int>> parent;
    int n;
    int m;
    LCA(int root_node,std::vector<std::vector<int>> &G):n((int)G.size()),m((int)(2+std::log(n)/std::log(2))){
        deep.resize(n),parent.assign(n,std::vector<int>(m));
        for(int i=0;i<n;i++){
            parent[i][0]=-1;
            deep[i]=-1;
        }
        deep[root_node]=0;
        parent[root_node][0]=-2;
        std::vector<int> order(n);
        order[0]=root_node;
        int look=1;
        for(int i=0;i<n;i++){
            for(auto x:G[order[i]]){
                if(deep[x]==-1){
                    deep[x]=deep[order[i]]+1;
                    parent[x][0]=order[i];
                    order[look]=x;
                    look++;
                }
            }
        }
        assert(look==n);//when G is not connected
        for(int i=0;i<n;i++) for(int j=1;j<m;j++){
            int var=order[i];
            if(parent[var][j-1]==-2) parent[var][j]=-2;
            else{
                parent[var][j]=parent[parent[var][j-1]][j-1];
            }
        }
    }
    int lca(int var_1,int var_2){
        if(deep[var_1]>deep[var_2]){
            std::swap(var_1,var_2);
        }
        int dif=deep[var_2]-deep[var_1];
        int ind=0;
        while(dif){
            if(dif&1){
                var_2=parent[var_2][ind];
            }
            ind++;
            dif>>=1;
        }
        if(var_1==var_2) return var_1;
        for(int i=m-1;i>=0;i--){
            if(parent[var_1][i]!=parent[var_2][i]){
                var_1=parent[var_1][i];
                var_2=parent[var_2][i];
            }
        }
        return parent[var_1][0];
    }
    int back(int var_1,int dif){
        for(int i=0;i<m;i++){
            if(dif==0) break;
            if(dif&1){
                var_1=parent[var_1][i];
            }
            dif>>=1;
        }
        return var_1;
    }
    // https://atcoder.jp/contests/abc267/tasks/abc267_f
    // if dist(var_1,var_2) < d ... return -1
    // return x 
    //    s.t dist(var_1, x) = d
    //        dist(var_2, x) = dist(var_1, var_2) - d
    int step(int var_1,int var_2,int d){
        int c=lca(var_1,var_2);
        int len=deep[var_1]+deep[var_2]-2*deep[c];
        if(len<d) return -1;
        if(deep[var_1]-deep[c]>=d) return back(var_1,d);
        return back(var_2,len-d);
    }
    int distance(int var_1,int var_2){
        int ascent=lca(var_1,var_2);
        return deep[var_1]+deep[var_2]-2*deep[ascent];
    }
};
}
using po167::LCA;


namespace atcoder {

namespace internal {

// @param n `0 <= n`
// @return minimum non-negative `x` s.t. `n <= 2**x`
int ceil_pow2(int n) {
    int x = 0;
    while ((1U << x) < (unsigned int)(n)) x++;
    return x;
}

// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
int bsf(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}

}  // namespace internal

template <class S,
          S (*op)(S, S),
          S (*e)(),
          class F,
          S (*mapping)(F, S),
          F (*composition)(F, F),
          F (*id)()>
struct lazy_segtree {
  public:
    lazy_segtree() : lazy_segtree(0) {}
    lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
    lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) {
        log = internal::ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        lz = std::vector<F>(size, id());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        return d[p];
    }

    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return e();

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push(r >> i);
        }

        S sml = e(), smr = e();
        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }

        return op(sml, smr);
    }

    S all_prod() { return d[1]; }

    void apply(int p, F f) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = mapping(f, d[p]);
        for (int i = 1; i <= log; i++) update(p >> i);
    }
    void apply(int l, int r, F f) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return;

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        {
            int l2 = l, r2 = r;
            while (l < r) {
                if (l & 1) all_apply(l++, f);
                if (r & 1) all_apply(--r, f);
                l >>= 1;
                r >>= 1;
            }
            l = l2;
            r = r2;
        }

        for (int i = 1; i <= log; i++) {
            if (((l >> i) << i) != l) update(l >> i);
            if (((r >> i) << i) != r) update((r - 1) >> i);
        }
    }

    template <bool (*g)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return g(x); });
    }
    template <class G> int max_right(int l, G g) {
        assert(0 <= l && l <= _n);
        assert(g(e()));
        if (l == _n) return _n;
        l += size;
        for (int i = log; i >= 1; i--) push(l >> i);
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!g(op(sm, d[l]))) {
                while (l < size) {
                    push(l);
                    l = (2 * l);
                    if (g(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*g)(S)> int min_left(int r) {
        return min_left(r, [](S x) { return g(x); });
    }
    template <class G> int min_left(int r, G g) {
        assert(0 <= r && r <= _n);
        assert(g(e()));
        if (r == 0) return 0;
        r += size;
        for (int i = log; i >= 1; i--) push((r - 1) >> i);
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!g(op(d[r], sm))) {
                while (r < size) {
                    push(r);
                    r = (2 * r + 1);
                    if (g(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

  private:
    int _n, size, log;
    std::vector<S> d;
    std::vector<F> lz;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
    void all_apply(int k, F f) {
        d[k] = mapping(f, d[k]);
        if (k < size) lz[k] = composition(f, lz[k]);
    }
    void push(int k) {
        all_apply(2 * k, lz[k]);
        all_apply(2 * k + 1, lz[k]);
        lz[k] = id();
    }
};

}  // namespace atcoder
using namespace atcoder;


struct lazy_S {
    ll x;
    ll y;
    ll size;
};

using lazy_F = pair<ll,ll>;

lazy_S lazy_op(lazy_S l, lazy_S r) {
    return lazy_S{
		l.x+r.x,l.y+r.y,l.size+r.size
    };
}

lazy_S lazy_e() { return lazy_S{0, 0, 0}; }

lazy_S mapping(lazy_F l, lazy_S r) {
	return {r.x+l.first*r.size,r.y+l.second*r.size,r.size};
}

//l(r(x))
lazy_F composition(lazy_F l, lazy_F r) {
    return {l.first+r.first,l.second+r.second};
}

lazy_F lazy_id(){return {0,0};}

#define lazy_calc lazy_S,lazy_op,lazy_e,lazy_F,mapping,composition,lazy_id


void solve();
// oddloop
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t=1;
    //cin>>t;
    rep(i,0,t) solve();
}

void solve(){
    int N,Q;
    cin>>N>>Q;
    vector<ll> A(N);
    rep(i,0,N) cin>>A[i];
    vector<vector<int>> G(N);
    rep(i,0,N-1){
        int a,b;
        cin>>a>>b;
        a--,b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    LCA L(0,G);
    vector<vector<int>> H(N);
    vector<int> size(N,1),pare(N,-1),nx(N);
    pare[0]=-2;
    rep(i,0,N) nx[i]=i;
    auto dfs_size=[&](auto self,int root) -> void {
        for(auto x:G[root]) if(pare[x]==-1){
            pare[x]=root;
            H[root].push_back(x);
            self(self,x);
            size[root]+=size[x];
        }
        sort(all(H[root]),[&](int l,int r){return size[l]>size[r];});
    };
    dfs_size(dfs_size,0);
    vector<int> order,inv(N);
    auto pb=[&](int a) -> void {
        inv[a]=order.size();
        order.push_back(a);
    };
    pb(0);
    auto dfs_order=[&](auto self,int var) -> void {
        if(H[var].empty()) return;
        pb(H[var][0]);
        self(self,H[var][0]);
        nx[H[var][0]]=nx[var];
        rep(i,1,H[var].size()) pb(H[var][i]);
        rep(i,1,H[var].size()) self(self,H[var][i]);
    };
    dfs_order(dfs_order,0);
    lazy_segtree<lazy_calc> seg(N);
    auto add=[&](int ind,ll val) -> void {
        // x(only)
        seg.apply(inv[ind],{val,0});
        // y(round)
        if(ind){
            seg.apply(inv[pare[ind]],{0,val});
        }
        seg.apply(inv[ind],{0,val});
        if(!H[ind].empty()){
            seg.apply(inv[ind]+1,{0,val});
            if(int(H[ind].size())>=2){
                seg.apply(inv[H[ind][1]],inv[H[ind][1]]+int(H[ind].size())-1,{0,val});
            }
        }
    };
    rep(i,0,N) seg.set(i,{0,0,1});
    rep(i,0,N) add(i,A[i]);
    auto del=[&](lazy_S l,lazy_S r) -> lazy_S {
        return {l.x-r.x,l.y-r.y,l.size-r.size};
    };
    auto get=[&](int ind) -> lazy_S {
        return seg.get(inv[ind]);
    };
    auto root_path=[&](int ind) -> lazy_S {
        lazy_S res=lazy_e();
        while(ind>=0){
            int n_ind=nx[ind];
            res=lazy_op(res,seg.prod(inv[n_ind],inv[ind]+1));
            ind=pare[n_ind];
        }
        return res;
    };
    auto path=[&](int l,int r) -> lazy_S {
        int c=L.lca(l,r);
        lazy_S res=lazy_op(root_path(l),root_path(r));
        auto tmp=root_path(c);
        res=del(res,lazy_op(tmp,tmp));
        res=lazy_op(res,get(c));
        res.y+=get(l).x;
        res.y+=get(r).x;
        return res;
    };
    rep(rp,0,Q){
        int t;
        cin>>t;
        if(t==0){
            int v,x;
            cin>>v>>x;
            add(v-1,x);
        }
        else{
            int u,v;
            cin>>u>>v;
            auto tmp=path(u-1,v-1);
            cout<<tmp.y-tmp.x*2ll<<"\n";
        }
    }
}
yukicoder

結果

ソースコード
