$STO\ \ \ \ \ ZYZ \ \ \ \ ORZ$

一些概念

首先我们引入几个(形同虚设)的概念orz
重儿子:父亲节点的所有儿子中子树结点数目最多的结点
轻儿子:父亲节点中除了重儿子以外的儿子
重边:父亲结点和重儿子连成的边
轻边:父亲节点和轻儿子连成的边
重链:由多条重边连接而成的路径
轻链:由多条轻边连接而成的路径

85ccfbe898fa4c37be020730cab5ca6f.png

举个例子:
此时蓝色结点为根结点
黄色的是轻儿子
绿色的是重儿子

黑色的$<1,2>,<2,5>,<3,6>$是轻边
红色的$<1,3>,<2,4>,<3,7>,<7,8>$是重边

$1-2-5$,$3-6$是轻链
$1-3-7-8$,$2-4$,$5$,$6$是重链

重链还有一个起点,如$1-3-7-8$的起点是$1$,$2-4$的起点是$2$。

我们把它记为结点的$top$值,一个轻儿子开头的$top$值是这个轻儿子自己。

第一次DFS

这次$dfs$,我们将完成以下几件事:

记录子树大小$size$,重儿子$son$,父亲结点$fa$,深度$dep$。

真让人瑟($size$)瑟($son$)发($fa$)抖($dep$)。

void dfs1(int x,int pre){
    size[x]=1;
    fa[x]=pre;
    dep[x]=dep[pre]+1;
    int maxson=0;
    for(int i=first[x];i;i=line[i].nextt){
        int y=line[i].to;
        if(y==pre) continue;
        dfs1(y,x);
        size[x]+=size[y];
        if(size[y]>maxson){
            son[x]=y;
            maxson=size[y];
        }
    }
}
第二次DFS

这次$dfs$,我们将完成以下几样事情:
记录所在重链起点$top$,对应新编号$id$,新编号的权值$nw$。

你看它们像不像一个$int$?

void dfs2(int x,int s){
    id[x]=++cnt;
    nw[cnt]=w[x];
    top[x]=s;
    if(size[x]==1) return;
    //叶子节点没有儿子,这里有必要判断一下。
    dfs2(son[x],s);
    for(int i=first[x];i;i=line[i].nextt){
        int y=line[i].to;
        if(son[x]==y) continue;
        if(fa[x]==y) continue;
        dfs2(y,y);
    }
}
一些规律

一个子树以下的所有结点的新编号组成的序列都会是连续的,且该子树的所有点新编号形成的区间将会是:

$$ [根结点所对应的新编号,根结点所对应的新编号+这棵树的结点数目-1] $$

f4caebc331c0f846b73cbd9a8dbecda5.png

我们拿三号节点为根结点的子树举个例子,它的新编号(红色的那个)将会是$3-2,7-3,8-4,6-5$,且重链的新编号

为$[2,4]$,子树的新编号的区间$[2,5]$将会是$[3结点的新编号2,2+结点数目4-1]$。

所以如果要求重链$3-7-8$各点的权值和,我们就直接求新编号连续区间$[2,4]$的和。

如果要求以$3$为根结点的子树的权值和,我们就直接求新编号连续区间$[2,5]$的和。

然后我们就想到了线段树$orz$。

复习下线段树吧
int a[4*maxn];//记录每个区间的左端点
int b[4*maxn];//记录每个区间的右端点
int sum[4*maxn];//记录每个区间和
int sign[4*maxn];//懒标记
#define ls(k) (k)<<1//计算左儿子编号
#define rs(k) (k)<<1|1//计算右儿子编号
void push_up(int k){
    sum[k]=sum[ls(k)]+sum[rs(k)];    
}
void build(int k,int l,int r){
    a[k]=l;b[k]=r;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(ls(k),l,mid);
    build(rs(k),mid+1,r);
    push_up(k);
} 
void update(int k,int dx){
    sum[k]+=(b[k]-a[k]+1)*dx;
    sign[k]+=dx;
}
void pushdown(int k){
    if(sign[k]==0) return;
    update(ls(k),sign[k]);
    update(rs(k),sign[k]);
    sign[k]=0;
}
void add(int k,int x,int y,int dx){
    if(a[k]>=x&&b[k]<=y){update(k,dx);return;}
    pushdown(k);
    int mid=(a[k]+b[k])>>1;
    if(x<=mid) add(ls(k),x,y,dx);
    if(y>mid) add(rs(k),x,y,dx);
    push_up(k);
}
int ask(int k,int x,int y){
    int ans=0;
    if(a[k]>=x&&b[k]<=y) return sum[k]; 
    pushdown(k);  
    int mid=(a[k]+b[k])>>1;
    if(x<=mid) ans+=ask(ls(k),x,y);
    if(y>mid) ans+=ask(rs(k),x,y);    
    return ans;
}
修改/查询将树从x到y结点最短路径上所有结点的值

我们让$x,y$的$top$深度更深的先跳,然后把跳的这一条链上的权值区间修改$d$(因为重链上的结点序号在新树上是连续的所以很好修改),然后把跳完后的结点更新为它$top$结点的父亲结点$fa$,然后再继续跳...然后直到最后$x,y$结点的$top$值相等,也就是$x,y$到了同一条重链上,因为结点序号还是连续的,所以我们仍然用线段树区间修改那条链上的权值。

void upd_edge(int x,int y,int d){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        add(1,id[top[x]],id[x],d);
        x=fa[top[x]];
    }
    if(dep[x]<dep[y]) swap(x,y);
    add(1,id[y],id[x],d);
}

查询差不多,$add$改成$ask$就行了。

int ask_edge(int x,int y){
    int ans=0;    
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        ans+=ask(1,id[top[x]],id[x]);ans%=mod;
        x=fa[top[x]]; 
    }
    if(dep[x]<dep[y]) swap(x,y);
    ans+=ask(1,id[y],id[x]);ans%=mod;
    return ans;
}
修改/查询以x为根子树所有结点的值

前面说的很详细了....

void upd_tree(int x,int d){
    add(1,id[x],id[x]+size[x]-1,d);
}
int ask_tree(int x){
    return ask(1,id[x],id[x]+size[x]-1);
}