模板汇总——树刨

佚名 6年前 (2019-04-23) 随笔 1294人围观抢沙发百度已收录

void dfs1(int o, int u){
    sz[u] = 1;
    for(int i = head[u]; ~i; i = nt[i]){
        int v = to[i];
        if(v == o) continue;
        dfs1(u, v);
        if(sz[v] > sz[son[u]]) son[u] = v;
        sz[u] += sz[v];
    }
}
void dfs2(int o, int u, int t){
    deep[u] = deep[o] + 1;
    top[u] = t;
    fa[u] = o;
    dfn[u] = ++dtot;
    dto[dtot] = u;
    if(son[u]) dfs2(u, son[u], t);
    for(int i = head[u]; ~i; i = nt[i]){
        int v = to[i];
        if(v == o || v == son[u]) continue;
        dfs2(u, v, v);
    }
}
int Query(int x, int l, int r, int rt){
    if(l == r)
        return tr[rt];
    int m = l+r >> 1;
    PushDown(rt);
    if(x <= m) return Query(x, lson);
    return Query(x, rson);
}
void Updata(int L, int R, int C, int l, int r, int rt){
//    cout << L << " l with r " << r <<  endl;
    if(L <= l && r <= R){
        lz[rt] += C;
        tr[rt] += C;
        return ;
    }
    int m = l+r >> 1;
    PushDown(rt);
    if(L <= m) Updata(L, R, C, lson);
    if(m < R) Updata(L, R, C, rson);
    return ;
}
void Updata_Path(int x, int y, int c){
    int fx = top[x], fy = top[y];
    while(fx != fy){
        if(deep[fx] > deep[fy]){
            Updata(dfn[fx],dfn[x],c,1,n,1);
            x = fa[fx]; fx = top[x];
        }
        else {
            Updata(dfn[fy],dfn[y],c,1,n,1);
            y = fa[fy]; fy = top[y];
        }
    }
    if(deep[x] < deep[y]) Updata(dfn[x], dfn[y], c, 1, n, 1);
    else Updata(dfn[y], dfn[x], c, 1, n,1);
}
void init(){
    memset(head, -1, sizeof(head));
    memset(son, 0, sizeof son);
    tot = dtot = 0;
}
void Ac(){
    dfs1(1,1);
    dfs2(1,1,1);
    Build(1,n,1);
}