[2020wc Day2] F. Clarice picking mushrooms (subtree and query, light and heavy son thought)

The question ：

Given a tree $n$ A little bit ,$n-1$ Undirected graph with edge weight of strip edge , The dots on the graph can grow mushrooms . Clarice starts at $1$.
Then happen $q$ Secondary event . There are two kinds of events ：

• $1vx$ It means at the point $v$ On the new long $x$ A mushroom .
• $2v$ Indicates that Clarice's starting position has become a dot $v$.

After each event , Clarice wanted to know the price of all the mushrooms she collected .
For any mushroom , The price of collecting it is the edge weight of the edge closest to Clarice's starting point on the path from the point where the mushroom is located to Clarice's starting point .

Data range ：$1\le n\le 10^6$,$1\le q\le 10^6$

Ideas ：

We divide the cost contribution of the starting point into three categories , Even father's side , Lian Chong's son's side , Even light son's side .
Consider one of these points as a starting point , The contribution of the side connected with the father is the total number of mushrooms at other points except this idea tree . We only need to be able to handle subtrees and queries （dfs order + Tree array ） That's it , Then the number of contributions is the subtree of the root and the subtree of this point .
Then consider the contribution times of the side of the heavy son , It's the son's tree and .
Finally, the contribution of light son , Because there are many young sons , We can't enumerate . When we consider adding mushrooms to a young son , Just jump on the edge of violence , Add your contribution to every point you jump to . The number of such jumps is $logn$ Of .
The final complexity is $o(nlogn)$.

Code ：

Another day .
（upd： Fixed the problem of jumping from light edge to heavy edge bug, For the heavy chain, we maintain a top Array chainhead , You can skip the heavy chain directly ）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1000000;
ll c[1000005];
void add(ll x,ll k) {
    
    while(x<=N) {
    
        c[x]+=k;
        x+=x&-x;
    }
}
ll getSum(ll x) {
    
    ll res=0;
    while(x>0) {
    
        res+=c[x];
        x-=x&-x;
    } return res;
}
ll val[1000005],sum[1000005];
ll fa[1000005],siz[1000005],son[1000005];
vector<ll>v[1000005],g[1000005];
ll id[1000005],idd;
void dfs(ll x,ll pre)
{
    
    id[x]=++idd;
    fa[x]=pre;
    siz[x]=1;
    for(ll i=0;i<v[x].size();i++)
    {
    
        ll to=v[x][i],w=g[x][i];
        if(to!=pre)
        {
    
            dfs(to,x);
            val[to]=w;
            siz[x]+=siz[to];
        }
    }
    for(ll to:v[x])if(to!=pre)
    {
    
        if(son[x]==0||siz[to]>siz[son[x]])son[x]=to;
    }
}
ll top[1000005];
void dfstop(ll x,ll pre)
{
    
    if(son[pre]==x)top[x]=top[pre];
    else top[x]=x;
    for(ll i=0;i<v[x].size();i++)
    {
    
        ll to=v[x][i];
        if(to!=pre)
        {
    
            dfstop(to,x);
        }
    }
}
int main()
{
    
	ll n;
	scanf("%lld",&n);
	for(ll i=1;i<n;i++)
    {
    
        ll a,b,w;
        scanf("%lld%lld%lld",&a,&b,&w);
        v[a].push_back(b);
        v[b].push_back(a);
        g[a].push_back(w);
        g[b].push_back(w);
    }
    dfs(1,0);
    dfstop(1,0);
    ll q;
    scanf("%lld",&q);
    int now=1;
    while(q--)
    {
    
        ll opt;
        scanf("%lld",&opt);
        if(opt==1)
        {
    
            ll v,x;
            scanf("%lld%lld",&v,&x);
            add(id[v],x);
            while(v!=0)
            {
    
                sum[fa[top[v]]]+=x*val[v];
                v=fa[top[v]];
            }
        }
        else
        {
    
            ll v;
            scanf("%lld",&v);
            now=v;
        }
        ll ans=val[now]*(getSum(n)-(getSum(id[now]+siz[now]-1)-getSum(id[now]-1)))+val[son[now]]*(getSum(id[son[now]]+siz[son[now]]-1)-getSum(id[son[now]]-1))+sum[now];
        printf("%lld\n",ans);
    }
	return 0;
}
/* 6 1 2 1 1 4 1 2 3 1 4 5 1 5 6 1 1 1 3 1 */