[树链剖分,LCA,换根]CF916E Jamie and Tree

前置知识：线段树树链剖分 LCA
题目： CF916E Jamie and Tree

题意：

有一棵n个节点的有根树，标号为1-n，你需要维护以下三种操作

给定一个点v，将整颗树的根变为v
给定两个点u, v，寻找最小子树包含u,v的点并把该树的子树加上x
给定一个点v，你需要回答以v所在的子树的权值和

题解:

分析题目，如果将第一个操作去除那么其实就是树链剖分的裸题，对于第二个操作可以直接使用LCA来找出该点，因为只需要找到两个点中的最近公共祖先即可。

那么加上第一个操作,也就是将整颗树换根，暴力的想每次换根重新计算一次dfs不太现实,那么可以在初始时将1做为树的根结点之后换根时以一个root变量来记录,之后的操作以root和原始根1来进行计算。

我们先讨论加上换根之后第3个操作如何实现。

首先分类讨论

如果要找的点v刚好是root则直接输出整颗树的和
如果v是root的子树中的一个值，则直接找v的子树即可，因为不敢如何根的子树范围是不会变的如图

如果是在root子树之上则需要找到对于v点所在的一个子结点包括root点的点，有点抽象看图吧

以上就是换根后的需要注意的点

ll lca(ll x, ll y){
    while(top[x] != top[y]){
        if(deep[top[x]] < deep[top[y]]) swap(x, y);
        if(fas[top[x]] == y) return top[x];
        x = fas[top[x]];
    }
    if(dfn[x] > dfn[y]) swap(x, y);
    return wson[x];
}
ll querys(ll x){
    if(x == root) return tree[1];
    if(dfn[x] <= dfn[root] && dfn[root] <= dfn[x] + sz[x] - 1){
        ll v = lca(x, root);
            ll ans = query(1, 1, n, 1, n);
            ans -= query(1, 1, n, dfn[v], dfn[v] + sz[v] - 1);
        return ans;
    }
    return query(1, 1, n, dfn[x], dfn[x] + sz[x] - 1);
}

之后我们再讨论对于u和v的修改操作

还是分类讨论

如果x和y在root子树，则点LCA(x, y) 就是换根之后需要修改的值
x和y其中一个在root的子树中，那么要修改的子树点必定是root
x和y不在root子树中，那么需要x和y 与root之间的关系,也就是它们到达的最低点p，u，分别代表x和root之间的lca和y和root之间的lca 中层次最大的点

ll LCA(ll x, ll y ){
    while(top[x] != top[y]){
        if(deep[top[x]] < deep[top[y]]) swap(x, y);
        x = fas[top[x]];
    }
    if(deep[x] > deep[y]) swap(x, y);
    return x;
}
void up_tree(ll x, ll y, ll v){
    ll as = LCA(x, root), bs = LCA(y, root), cs = LCA(x, y);
    ll vs = as;
    if(deep[vs] <= deep[bs]) vs = bs;
    if(deep[vs] <= deep[cs]) vs = cs;
    if(vs == root) {
        update(1, 1, n, 1, n, v);
        return;
    }
    if(dfn[vs] <= dfn[root] && dfn[root] <= dfn[vs] + sz[vs] - 1){
        ll pp = lca(vs, root);
        update(1, 1, n, 1, n, v);
        vs = pp;
        update(1, 1, n, dfn[vs], dfn[vs] + sz[vs] - 1, -v);
        return;
    }
    update(1, 1, n, dfn[vs], dfn[vs] + sz[vs] - 1, v);
    return;
}

复杂度: O(nmlogn)

完整代码

const long long inf=1e18;
const int N= 7e5 + 10;
const int M= 2e5 + 10;
const ll mod=1e9+7;
using namespace std;
ll n, q;
ll a[N];
struct Node{
    ll to, nxt;
}e[N];
ll head[N], tot = 0;
void add(ll a, ll b){
    e[tot].to = b;
    e[tot].nxt = head[a];
    head[a] = tot ++;
}
ll wson[N], sz[N], dfn[N], deep[N], fas[N], pre[N], top[N];
void dfs1(ll to, ll fa){
    sz[to] = 1;
    deep[to] = deep[fa] + 1;
    fas[to] = fa;
    for(ll i = head[to]; i + 1; i = e[i].nxt){
        ll y = e[i].to;
        if(y == fa) continue;
        dfs1(y, to);
        sz[to] += sz[y];

        if(sz[wson[to]] < sz[y]) wson[to] = y;
    }
}
ll cnt =0 ;
void dfs2(ll to, ll de){
    dfn[to] = ++ cnt;
    pre[cnt] = to;
    top[to] = de;
    if(wson[to]) dfs2(wson[to], de);
    else return ;
    for(ll i = head[to]; i + 1; i = e[i].nxt){
        ll y = e[i].to;
        if(y == fas[to] || y == wson[to]) continue;
        dfs2(y, y);
    }
}
ll tree[N], lazy[N];
void build(ll rt, ll l, ll r){
    if(l == r) {
        tree[rt] += a[pre[l]];
        return;
    }
    ll mid = (l + r) >> 1;
    build(rt << 1, l, mid);
    build(rt << 1 | 1, mid + 1, r);
    tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
}
void push_lazy(ll rt, ll l, ll r){
    if(lazy[rt]){
        lazy[rt << 1] += lazy[rt];
        lazy[rt << 1 | 1] += lazy[rt];
        ll mid = (l + r) >> 1;
        ll ls = l, rs = mid;
        tree[rt << 1] += (rs - ls + 1) * lazy[rt];
        ls = mid + 1; rs = r;
        tree[rt << 1 | 1] += (rs - ls + 1) * lazy[rt];
        lazy[rt] = 0;
    }
}
void update(ll rt, ll l, ll r, ll L, ll R, ll v){
    if(L <= l && r <= R){
        tree[rt] += (r - l + 1) * v;
        lazy[rt] += v;
        return;
    }
    ll mid = (l + r) >> 1;
    push_lazy(rt, l, r);
    if(L <= mid) update(rt << 1, l, mid, L, R, v);
    if(mid < R) update(rt << 1 | 1, mid + 1, r, L, R, v);
    push_lazy(rt, l, r);
    tree[rt] = tree[rt << 1] + tree[rt << 1| 1];
}
ll root = 1;
ll LCA(ll x, ll y ){
    while(top[x] != top[y]){
        if(deep[top[x]] < deep[top[y]]) swap(x, y);
        x = fas[top[x]];
    }
    if(deep[x] > deep[y]) swap(x, y);
    return x;
}
ll lca(ll x, ll y){
    while(top[x] != top[y]){
        if(deep[top[x]] < deep[top[y]]) swap(x, y);
        if(fas[top[x]] == y) return top[x];
        x = fas[top[x]];
    }
    if(dfn[x] > dfn[y]) swap(x, y);
    return wson[x];
}
ll get(ll x){
    ll v = root;
    while(top[v] != top[x]){
        if(fas[top[v]] == x) return top[v];
        v = fas[top[v]];
    }
    return wson[x];
}
void up_tree(ll x, ll y, ll v){
    ll as = LCA(x, root), bs = LCA(y, root), cs = LCA(x, y);
    ll vs = as;
    if(deep[vs] <= deep[bs]) vs = bs;
    if(deep[vs] <= deep[cs]) vs = cs;
    if(vs == root) {
        update(1, 1, n, 1, n, v);
        return;
    }
    if(dfn[vs] <= dfn[root] && dfn[root] <= dfn[vs] + sz[vs] - 1){
        ll pp = lca(vs, root);
        update(1, 1, n, 1, n, v);
        vs = pp;
        update(1, 1, n, dfn[vs], dfn[vs] + sz[vs] - 1, -v);
        return;
    }
    update(1, 1, n, dfn[vs], dfn[vs] + sz[vs] - 1, v);
    return;
}
ll query(ll rt, ll l, ll r, ll L, ll R){
    if(L <= l && r <= R) return tree[rt];
    ll mid = (l + r) >> 1;
    push_lazy(rt, l, r);
    ll ans = 0;
    if(L <= mid) ans += query(rt << 1, l, mid, L, R);
    if(mid < R) ans += query(rt << 1 | 1, mid + 1, r, L, R);
    push_lazy(rt, l, r);
    tree[rt] =  tree[rt << 1 | 1] + tree[rt << 1];
    return ans;
}
ll querys(ll x){
    if(x == root) return tree[1];
    if(dfn[x] <= dfn[root] && dfn[root] <= dfn[x] + sz[x] - 1){
        ll v = lca(x, root);
            ll ans = query(1, 1, n, 1, n);
            ans -= query(1, 1, n, dfn[v], dfn[v] + sz[v] - 1);
        return ans;
    }
    return query(1, 1, n, dfn[x], dfn[x] + sz[x] - 1);
}
int main(){
    RLL2(n, q);
    MM(head, -1);
    FOR(i, 1, n) RLL(a[i]);
    FOR(i, 1, n - 1) {
        ll l, r;
        RLL2(l, r);
        add(l, r);add(r, l);
    }
    dfs1(1, 0);
    dfs2(1, 1);
    build(1, 1, n);
    while(q --){
        ll k; RLL(k);
        if(k == 1){
            RLL(root);
        }else if(k == 2){
            ll l, r, v;
            RLL3(l, r, v);
            up_tree(l, r, v);
        }else{
            ll v; RLL(v);
            PLN(querys(v));
        }
    }
    return 0;
}

[树链剖分,LCA,换根]CF916E Jamie and Tree

题意：

题解:

完整代码

感谢您的支持，我会继续努力的!