838B - Diverging Directions - CodeForces Solution

/** * * * * * * * * * * * * * * * **\
 *                                 *
 *     Author: Haidara Nassour     *
 *  Coded in: YYYY\MM\DD HH:MM:SS  *
 *         Language: C++22         *
 *                                 *
\** * * * * * * * * * * * * * * * **/
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long
#define itn int
#define endl '\n'
#define rep(i,x,n) for(int i=(x);i<(n);i++)
#define FOR(i,n) rep(i,0,n)
#define repf(i,x,n) for(int i=(x);(n);i++)
#define per(i,x,n) for(int i=(x);i>(n);i--)
#define ROF(i,x) for(int i=x;i>=0;i--)
#define v(i) vector< i >
#define p(i,j) pair< i , j >
#define pii pair<int,int>
#define m(i,j) map< i , j >
#define um(i,j) unordered_map< i , j >
#define max_heap(i) priority_queue< i >
#define min_heap(i) priority_queue< i , vector< i > ,greater< i > >
#define ff first
#define sinf(x) const int inf=x;
#define smaxn(x) const int maxn=x;
#define ss second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pp push_back
#define mini(x,y) x=min(x,y)
#define maxi(x,y) x=max(x,y)
#define debug(x) cout<<endl<<#x<<"="<<x<<endl;
#define point(x) complex< x >
#define X real()
#define mp make_pair
#define Y imag()
#define add(x,y) x=(x+(y%mod))%mod
using namespace std;
using namespace __gnu_pbds;
void SIO(string name="",string name2="",string later="",string later2="")
{
    if(later=="")
    {
        later=".in";
        later2=".out";
    }
    else
    {
        if(later2=="")
            later2=later;
    }
    if(name!="")
    {
        if(name2=="")
            freopen((name+later).c_str(),"r",stdin);
        else
        {
            freopen((name+later).c_str(),"r",stdin);
            freopen((name2+later2).c_str(),"w",stdout);
        }
    }
}
template <class T> using o_set = tree<T, null_type, less<T>,rb_tree_tag, tree_order_statistics_node_update>;
template <class T> using o_multiset = tree<T, null_type, less_equal<T>,rb_tree_tag, tree_order_statistics_node_update>;
///order_of_key = find index of element x ( returned val is integer )
///find_by_order = find value at index x ( returned val is pointer )
/// to swap s1 and s2 we make the following: s1.swap(s2)
template<class T> T chmin(T &a,T b)
{
    if(b<a)
        a=b;
    return a;
}
template<class T> T chmax(T &a,T b)
{
    if(a<b)
        a=b;
    return a;
}
template<class T> T mxmn(T &a,T &b)
{
    int mx=max(a,b);
    int mn=min(a,b);
    a=mx,b=mn;
    return mx+mn;
}
const double pi=2.0*acos(0.0);
const double memory=1048576.0;
const int inf=1LL<<50LL;
const int mod=1e9+7;
const int maxn=200100;
int n;
v(pii)graph[maxn];
int euler[maxn],par[maxn][25],lev[maxn],sz[maxn],pos[maxn],to1[maxn],id[maxn];
v(int)mn(maxn,inf);
int tim=1;
void dfs(int st=1,int pa=-1,int dist=0,int depth=0)
{
    lev[st]=depth;
    par[st][0]=pa;
    sz[st]=1;
    pos[st]=tim++;
    mn[pos[st]]=dist+to1[st];
    euler[pos[st]]=dist;
    for(auto i:graph[st])
    {
        int u=i.ff;
        int w=i.ss;
        if(u==pa)
            continue;
        dfs(u,st,dist+w,depth+1);
        sz[st]+=sz[u];
    }
}
struct node
{
    int val,lazy;
    node()
    {
        val=0,lazy=0;
    }
} st[maxn*4],st2[maxn*4];
void pull(int inx,int l,int r)
{
    st[inx].val+=st[inx].lazy*(r-l+1);
    if(l!=r)
    {
        st[inx*2].lazy+=st[inx].lazy;
        st[inx*2+1].lazy+=st[inx].lazy;
    }
    st[inx].lazy=0;
}
void build(int l=1,int r=n,int inx=1)
{
    if(l==r)
    {
        st[inx].val=euler[l];
        return ;
    }
    int mid=l+(r-l)/2;
    build(l,mid,inx*2);
    build(mid+1,r,inx*2+1);
}
void update(int ql,int qr,int val,int l=1,int r=n,int inx=1)
{
    pull(inx,l,r);
    if(ql<=l&&r<=qr)
    {
        st[inx].lazy+=val;
        pull(inx,l,r);
        return ;
    }
    if(ql>r||l>qr)
        return ;
    int mid=l+(r-l)/2;
    update(ql,qr,val,l,mid,inx*2);
    update(ql,qr,val,mid+1,r,inx*2+1);
}
int query(int x,int l=1,int r=n,int inx=1)
{
    pull(inx,l,r);
    if(l==r)
        return st[inx].val;
    int mid=l+(r-l)/2;
    if(x<=mid)
        return query(x,l,mid,inx*2);
    return query(x,mid+1,r,inx*2+1);
}


void up(int inx)
{
    st2[inx].val=min(st2[inx*2].val,st2[inx*2+1].val);
}
void pull2(int inx,int l,int r)
{
    st2[inx].val+=st2[inx].lazy;
    if(l!=r)
    {
        st2[inx*2].lazy+=st2[inx].lazy;
        st2[inx*2+1].lazy+=st2[inx].lazy;
    }
    st2[inx].lazy=0;
}
void build2(int l=1,int r=n,int inx=1)
{
    st2[inx].val=inf;
    if(l==r)
    {
        st2[inx].val=mn[l];
        return ;
    }
    int mid=l+(r-l)/2;
    build2(l,mid,inx*2);
    build2(mid+1,r,inx*2+1);
    up(inx);
}
void update2(int ql,int qr,int val,int l=1,int r=n,int inx=1)
{
    pull2(inx,l,r);
    if(ql<=l&&r<=qr)
    {
        st2[inx].lazy+=val;
        pull2(inx,l,r);
        return ;
    }
    if(ql>r||l>qr)
        return ;
    int mid=l+(r-l)/2;
    update2(ql,qr,val,l,mid,inx*2);
    update2(ql,qr,val,mid+1,r,inx*2+1);
    up(inx);
}
int query2(int ql,int qr,int l=1,int r=n,int inx=1)
{
    pull2(inx,l,r);
    if(ql<=l&&r<=qr)
        return st2[inx].val;
    if(ql>r||l>qr)
        return inf;
    int mid=l+(r-l)/2;
    int res=min(query2(ql,qr,l,mid,inx*2),query2(ql,qr,mid+1,r,inx*2+1));
    up(inx);
    return res;
}
int lca(int a,int b)
{
    if(lev[a]<lev[b])
        swap(a,b);
    int dx=lev[a]-lev[b];
    FOR(i,25)
    if((1LL<<i)&dx)
        a=par[a][i];
    if(a==b)
        return a;
    for(int i=24; i>=0; i--)
        if(par[a][i]!=par[b][i])
            a=par[a][i],b=par[b][i];
    return par[a][0];
}
int get_dist(int a,int b)
{
    int anc=lca(a,b);
    return query(pos[a])+query(pos[b])-2*query(pos[anc]);
}
signed main()
{
    FAST;
    int q;
    cin>>n>>q;
    v(p(pii,int))e;
    FOR(i,n-1)
    {
        int a,b,c;
        cin>>a>>b>>c;
        e.pp({{a,b},c});
        graph[a].pp({b,c});
        graph[b].pp({a,c});
    }
    FOR(i,n-1)
    {
        int j,k;
        cin>>j>>k>>k;
        to1[j]=k;
        id[i]=j;
    }
    dfs();
    rep(i,1,25)
    FOR(j,n+1)
    par[j][i]=par[par[j][i-1]][i-1];
    build();
    build2();
    while(q--)
    {
        int t,a,b;
        cin>>t>>a>>b;
        if(t&1)
        {
            a--;
            if(a>=(int)e.size())
            {
                a-=(int)e.size();
                int dx=b-to1[id[a]];
                to1[id[a]]=b;
                update2(pos[id[a]],pos[id[a]],dx);
                continue;
            }
            int u=e[a].ff.ff;
            int v=e[a].ff.ss;
            int w=e[a].ss;
            if(par[u][0]==v)
                swap(u,v);
            int dx=b-w;
            e[a].ss=b;
            update(pos[v],pos[v]+sz[v]-1,dx);
            update2(pos[v],pos[v]+sz[v]-1,dx);
        }
        else
        {
            int anc=lca(a,b);
            if(anc==a)
                cout<<get_dist(a,b)<<endl;
            else
            {
                int mn=query2(pos[a],pos[a]+sz[a]-1);
                mn-=query(pos[a]);
                cout<<mn+query(pos[b])<<endl;
            }
        }
    }
}