采蘑菇的克拉莉丝

采蘑菇的克拉莉丝

传送门

题目大意

有一个\(N\)个点，\(N-1\)条边的无向联通图，一开始的起点在\(1\)号点，游戏过程中会发生两种事件：

• \(1、\)\(1\ v\ x(1\leq x\leq10^5)\)表示在编号为\(v\)的节点新出现了\(x\)个蘑菇
• \(2、\)\(2\ v\)表示起点变成了节点\(v\)

规定搜集每个蘑菇的代价为起点到这个蘑菇最短路径中最靠近起点的边的边权，在起点的蘑菇不需要代价就能搜集。现有\(Q\)个事件，每次事件发生后，你需要回答搜集所有蘑菇所需要的代价。\((1\leq N\leq10^6,1\leq Q\leq10^6)\)

思路

我们可以发现每次在一个点增加若干个蘑菇，这个点到点\(1\)的最短路径上的点的贡献都是由它与它某个儿子的连边产生的，而其他点的贡献是由它与它父亲的连边产生的。因此我们可以暴力更新轻儿子产生的贡献，然后对父亲和重儿子产生的贡献打标记，就可以了。而打标记我们可以用树链剖分加上线段树或者树状数组来做，然后就差不多结束了。

代码

#include
using namespace std;
const int maxn=1e6+5;
inline int read()
{
    int s=0,w=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar())if(ch=='-')w=-1;
    for (;ch>='0'&&ch<='9';ch=getchar())s=(s<<1)+(s<<3)+(ch^48);
    return (w==-1?-s:s);
}
int n;
struct EDGE
{
    int next,to,w;
}edge[maxn<<1];
int head[maxn];
int cnt;
void add(int u,int v,int w)
{
    edge[cnt].w=w;
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
int dep[maxn],siz[maxn],fa[maxn],son[maxn];
long long a[maxn];
void dfs1(int x,int father)
{
    dep[x]=dep[father]+1;
    int maxsiz=-1;
    for(int i=head[x];~i;i=edge[i].next)
    {
        int it=edge[i].to;
        if(it==father)continue;
        fa[it]=x;
        a[it]=edge[i].w;
        dfs1(it,x);
        siz[x]+=siz[it]+1;
        if(siz[it]>maxsiz)
        {
            maxsiz=siz[it];
            son[x]=it;
        }
    }
}
int top[maxn],id[maxn],tot;
void dfs2(int x,int tp)
{
    id[x]=++tot;
    top[x]=tp;
    if(son[x])dfs2(son[x],tp);
    for(int i=head[x]; i!=-1; i=edge[i].next)
    {
        int it=edge[i].to;
        if(it==fa[x])continue;
        if(it==son[x])continue;
        dfs2(it,it);
    }
}
long long ans[maxn],laz[3][maxn<<2];
void update(int p,int l,int r,int w,int x,int y,int op)
{
    if(x<=l&&r<=y)
    {
        laz[op][p]+=w;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid)update(p<<1,l,mid,w,x,y,op);
    if(mid>1;
    if(x<=mid)return query(p<<1,l,mid,x,y,cnt1+laz[1][p],cnt2+laz[2][p]);
    else return query(p<<1|1,mid+1,r,x,y,cnt1+laz[1][p],cnt2+laz[2][p]);
}
int main()
{
    n=read();
    memset(head,-1,sizeof(head));
    for(int i=1;i