𝗖𝗦 𝗔𝗹𝗴𝗼 💻 🌐 『𝗖𝗼𝗺𝗽𝗲𝘁𝗶𝘁𝗶𝘃𝗲 𝗣𝗿𝗼𝗴𝗿𝗮𝗺𝗺𝗶𝗻𝗴』

IBM✅
SQL

741 viewsDushyant, 07:28

#include <bits/stdc++.h>
#define ll long long
#define db double
#define fi first
#define se second
#define pb push_back
#define ppb pop_back
#define mk make_pair
#define pll pair<ll,ll>
#define pii pair<int,int>
#define pil pair<int,long long>
#define all(a) a.begin(),a.end()
#define tm template<class dt>
using namespace std;
using vi = vector<int>;
using vl = vector<ll>;
using vb = vector<bool>;
using ull = unsigned long long;
const int MOD = 1e9 + 7;
const db eps = 1e-9;
const db pi = acos(-1.0);
const int iinf = INT_MAX;
const ll inf = LLONG_MAX;
const long double f_inf = FLT_MAX;
#define debug(x) cout << #x << " " << x << "\n";
#define tC(t) for(int ti=1;ti<=t;ti++)
tm dt max_t(const dt &a,const dt &b){return (a>b)?a:b;}
tm dt min_t(const dt &a,const dt &b){return (a>b)?b:a;}
tm void swapx(dt &a,dt &b){a ^= b;b ^= a;a ^= b;}

struct Query{long long w;int u,v,idx;};
const int mxn = 1e5 + 10;
const int mxk = 20;
vi adj[mxn];
int tin[mxn],subt[mxn],lvl[mxn];
int dp[mxn][mxk],idx;

bool cmp(const Query &a,const Query &b){
    if(a.w==b.w)return a.idx==-1;
    else return a.w < b.w;
}

void dfs(int u = 1,int p = -1,int l = 0){
    dp[u][0] = p; tin[u] = idx++;
    subt[u] = 1; lvl[u] = l;
    for(int i=1;i<mxk;i++){
        if(dp[u][i-1]==-1)break;
        dp[u][i] = dp[dp[u][i-1]][i-1];
    }
    for(auto v: adj[u]){
        if(v==p)continue;
        dfs(v,u,l+1);
        subt[u] += subt[v];
    }
}

struct Segtree{
    vl t,lazy;
    Segtree(int N){
        t.assign(4 * N + 10, 0);
        lazy.assign(4 * N + 10, 0);
    }
    void Update(int v,int l,int r,int lb,int ub,ll x){
        if(lazy[v]){
            t[v] += (r - l + 1) * lazy[v];
            if(l!=r){
                lazy[2*v+1] += lazy[v];
                lazy[2*v+2] += lazy[v];
            }
            lazy[v] = 0;
        }
        if(r<lb ub<l ub<lb)return;
        if(l>=lb && r<=ub){
            t[v] += (r - l + 1) * x;
            if(l!=r){
                lazy[2*v+1] += x;
                lazy[2*v+2] += x;
            }
            return;
        }
        int m = l + (r-l)/2;
        Update(2*v+1,l,m,lb,ub,x);
        Update(2*v+2,m+1,r,lb,ub,x);
        t[v] = t[2*v+1] + t[2*v+2];
    }
    long long Query(int v,int l,int r,int index){
        if(lazy[v]){
            t[v] += (r - l + 1) * lazy[v];
            if(l!=r){
                lazy[2*v+1] += lazy[v];
                lazy[2*v+2] += lazy[v];
            }
            lazy[v] = 0;
        }
        if(l==r)return t[v];
        int m = l + (r-l)/2;
        if(index <= m)return Query(2*v+1,l,m,index);
        else return Query(2*v+2,m+1,r,index);
    }
};

int LCA(int a,int b){
    if(lvl[b] > lvl[a])swapx<int>(a,b);
    int dif = lvl[a] - lvl[b];
    for(int i=mxk-1;i>=0;i--){
        if(dif & (1ll<<i))a = dp[a][i];
    }
    if(a==b)return a;
    for(int i=mxk-1;i>=0;i--){
        if(dp[a][i]!=dp[b][i]){
            a = dp[a][i];
            b = dp[b][i];
        }
    }
    return dp[a][0];
}

void Solve(int ti){
    int N;
    cin >> N;
    long long w;
    int a,b;
    vector<Query> Q;
    for(int i=1;i<=N;i++){
        cin >> w;
        Q.pb({w,i,-1,-1});
    }
    for(int i=1;i<N;i++){
        cin >> a >> b;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    int q;
    cin >> q;
    for(int i=0;i<q;i++){
        cin >> a >> b >> w;
        Q.pb({w, a, b, i});
    }
    sort(all(Q),cmp);
    dfs();
    long long C[N+1],R[q];
    memset(C, 0, sizeof(C));
    Segtree st(N);
    int M = Q.size();
    for(int i=0;i<M;i++){
        if(Q[i].idx==-1){
            int u = Q[i].u; C[u] = Q[i].w;
            st.Update(0,0,N-1,tin[u],tin[u]+subt[u]-1,C[u]);
        }else{
            int lca = LCA(Q[i].u,Q[i].v);
            long long Sum = 0;
            Sum += st.Query(0,0,N-1,tin[Q[i].u]);
            Sum += st.Query(0,0,N-1,tin[Q[i].v]);

👍3

880 viewsDushyant, 13:58