Home

# CF1192B 题解

题目链接
跟着 duyidalao 的思路，轻而易举 (qian nan wan xian) 调出了本题。
既然 @ duyi 没放代码，那我就来一发吧。

# 题意简述

有一个 nn 个点的带权无向树， qq 次操作，每次修改一条边的权值，要求在每次修改后，输出树的直径大小，强制在线。

# 题目分析

  1. 对于两棵树合并后新树的直径，其两端点一定出自两树直径四个端点中，根据这一条性质我们就可以用线段树维护原树，自下向上合并节点就相当于合并它所代表的两棵子树。

  2. 每次合并的时候，需要我们计算树上两点间距离，记该节点到根的距离为 d⁡(x)\operatorname{d}(x) , 则 节点 xx 到 yy 的距离为 d⁡(x)+d⁡(y)−2×d⁡(lca⁡(x,y))\operatorname{d}(x)+\operatorname{d}(y)-2 \times \operatorname{d}(\operatorname{lca}(x, y)) 。在四个点的六组搭配中，选择直径最大的一组作为答案向上传递。

  3. 求树上到根的距离利用线段树 (这时候是区别于第一条的另一棵) 用两种选择，将边权化为点权后，一是单点修改加上区间查询，而是区间修改加上单点查询 (边权改变影响的只有子树，而子树在树剖后节点编号连续)。而这里我们采取后者。至于为什么不用前者... 血的教训。

# 思路实现

  1. 我们对求出原树的 dfs 序，同时记录以该节点为根的子树在 dfs 序中的开始和结束编号，记为 beg⁡(x)\operatorname{beg}(x) 和 end⁡(x)\operatorname{end}(x) , 对 dfs 序建立第一棵线段树。 该线段树维护树的直径。
  2. 对原树重链剖分，建第二棵线段树维护每个点到根的路径长。当然还要求 LCA 。
  3. 可以使用 unordered_map 记录下求过的 LCA, 用 map 会多一个 log⁡\log 的复杂度。

# Code

代码中函数名带有 '_1' 的为维护直径的线段树，带有 '_2' 的为维护到根距离的线段树。

树剖就不需要解释了吧 (

auto dfs1(int x, int fa) -> void
{
    f[x] = fa; siz[x] = 1;
    dep[x] = dep[fa]+1;
    int maxson = 0, y;
    for(int i = head[x]; i; i = a[i].next)
    {
        y = a[i].to; if(y == fa) continue;
        dfs1(y, x); siz[x] += siz[y];
        if(siz[y] > siz[maxson]) maxson = y;
    }
    son[x] = maxson;
}
auto dfs2(int x, int tp) -> void
{
    id[x] = ++tim; top[x] = tp;
    if(son[x]) 
    {
        dfs2(son[x], tp); int y;
        for(int i = head[x]; i; i = a[i].next)
        {
            y = a[i].to;
            if(y == f[x] or y == son[x]) continue;
            dfs2(y, y);
        }
    }
}
auto LCA(int x, int y) -> int
{
    while(top[x] != top[y])
    {
        if(dep[top[x]] < dep[top[y]]) y = f[top[y]]; 
        else x = f[top[x]];
    }
    if(id[x] > id[y]) return y;
    return x;
}

求 dfs 序

auto dfsx(int x) -> void
{
    d[++ct] = x;    //dfs 序数组
    beg[x] = ct;    // 子树起点
    for(int i = head[x], y; i; i = a[i].next)
    {
        y = a[i].to; if(y == f[x]) continue;
        dfsx(y);
    }
    ::end[x] = ct;  // 子树终点 (变量名 end 有冲突，所以加了作用域)
}

第一棵线段树

auto build_1(int l, int r, int i) -> void
{
    dr[i].l = l;
    dr[i].r = r;
    if(l == r) return (void)(dr[i].u = dr[i].v = d[l]);
    int mid = (l+r)>>1;
    build_1(l, mid, ls(i));
    build_1(mid+1, r, rs(i));
    pushup_1(i);
}
auto change_1(int l, int r, int i) -> void
{
    if(dr[i].l > r or dr[i].r < l) return ;
    if(dr[i].l >= l and dr[i].r <= r) return ;
    change_1(l, r, ls(i));
    change_1(l, r, rs(i));
    pushup_1(i);
}
auto pushup_1(int i) -> void
{
    lu = dr[ls(i)].u, lv = dr[ls(i)].v;
    ru = dr[rs(i)].u, rv = dr[rs(i)].v;
    /*  左右子树的较优解  */
    if(dr[ls(i)].val >= dr[rs(i)].val) 
        dr[i].u = dr[ls(i)].u, 
        dr[i].v = dr[ls(i)].v, 
        dr[i].val = dr[ls(i)].val; 
    else 
        dr[i].u = dr[rs(i)].u, 
        dr[i].v = dr[rs(i)].v, 
        dr[i].val = dr[rs(i)].val; 
    /*  枚举剩下四种情况  */
    U = lu, V = ru; 
    len = calc(U, V);
    if(ru != rv) // 重复的不计算了
    {   
        len2 = calc(lu, rv); 
        if(len2 > len) U = lu, V = rv, len = len2;
    }
    if(lu != lv) // 重复的不计算了
    {
        len2 = calc(lv, ru); 
        if(len2 > len) U = lv, V = ru, len = len2;
        if(ru != rv) // 重复的不计算了 
        {
            len2 = calc(lv, rv); 
            if(len2 > len) U = lv, V = rv, len = len2;
        }
    }
    if(len > dr[i].val) 
        dr[i].val = len, dr[i].u = U, dr[i].v = V;
}
auto calc(int x, int y) -> long
{
    int lca;
    /* 将 x,y 压入一个数，就不用 pair 了 */
    if( !mp.count(((long)(x)<<32ll)+y) ) mp[((long)(x)<<32ll)+y] = lca = LCA(x, y);
    else lca = mp[((long)(x)<<32ll)+y];
    return query_2(id[x], 1)+query_2(id[y], 1)-2*query_2(id[lca], 1);
}
第二棵线段树


auto build_2(int l, int r, int i) -> void
{
    tr[i].l = l;
    tr[i].r = r;
    if(l == r) return ;
    int mid = (l+r)>>1;
    build_2(l, mid, ls(i));
    build_2(mid+1, r, rs(i));
}
auto add_2(int l, int r, long k, int i) -> void
{
    if(tr[i].l > r or tr[i].r < l) return ;
    if(tr[i].l >= l and tr[i].r <= r) 
    {
        tr[i].lz += k;
        tr[i].val += k*(tr[i].r-tr[i].l+1);
        return ;
    }
    pushdown_2(i);
    add_2(l, r, k, ls(i));
    add_2(l, r, k, rs(i));
    tr[i].val = tr[ls(i)].val+tr[rs(i)].val;
}
auto query_2(int x, int i) -> long
{
    if(tr[i].l > x or tr[i].r < x) return 0;
    if(tr[i].l == x and tr[i].r == x) return tr[i].val;
    pushdown_2(i);
    return query_2(x, ls(i))+query_2(x, rs(i));
}
auto pushdown_2(int i) -> void
{
    if(!tr[i].lz) return ;
    tr[ls(i)].lz += tr[i].lz;
    tr[rs(i)].lz += tr[i].lz;
    tr[ls(i)].val += tr[i].lz*(tr[ls(i)].r-tr[ls(i)].l+1);
    tr[rs(i)].val += tr[i].lz*(tr[rs(i)].r-tr[rs(i)].l+1);
    tr[i].lz = 0;
}
接下来是主函数，得斯


auto main() -> signed
{
    scanf("%d%d%lld", &n, &q, &w);
    for(int i = 1; i < n; i += 1)
    {
        scanf("%d%d%lld", &u[i], &v[i], &c[i]);
        add_edge(u[i], v[i]);
        add_edge(v[i], u[i]);
    }
    dfs1(1, 0); dfs2(1, 1);  // 剖了它
    build_2(1, n, 1);        //_____
    for(int i = 1; i < n; i += 1)
    {
        if(dep[u[i]] > dep[v[i]])       // 加入初始边权
            add_2(id[u[i]], id[u[i]]+siz[u[i]]-1, c[i], 1);
        else  
            add_2(id[v[i]], id[v[i]]+siz[v[i]]-1, c[i], 1);
    }
    dfsx(1); 
    build_1(1, n, 1);
    for(int i = 1, D; i <= q; i += 1)
    {
        scanf("%d%lld", &D,&E);
        D = (D+lst)%(n-1)+1;
        E = (E+lst)%w;
        if(dep[u[D]] > dep[v[D]])  
        {
            add_2(id[u[D]], id[u[D]]+siz[u[D]]-1, E-c[D], 1);  // 权值的修改
            change_1(beg[u[D]], ::end[u[D]], 1);               // 直径的更新
            c[D] = E;
        }
        else 
        {
            add_2(id[v[D]], id[v[D]]+siz[v[D]]-1, E-c[D], 1);
            change_1(beg[v[D]], ::end[v[D]], 1);
            c[D] = E;
        }
        lst = dr[1].val;
        printf("%lld\n", lst);
    }
    return 0;
}
# 结语


常数有那么亿点点大。

若有什么问题欢迎评论或私信指出。

\Huge