树上分块

· · 题解

不同的分块思路

预处理

需要预处理每一个点到父亲的边权，记录下来，把他变成点权，便于维护。

同时把所有点按照层数储存

分块

从上到下按照层数大小分块。对于每一个点处理出这一个点不断向上跳到最近的和它所属块的编号不同的点是哪一个，以及他们间路径的最大值。

修改

直接改点权即可。改完点权把同属同一个块的子节点的信息都更新。因为同属一个块，所以他们最终跳到的都是同一个点，修改的点之上的路径都是同时经过的。

查询

类似于 LCA 的实现，我们可以先找到他们的 LCA ,然后开始往上跳，只要不处于同一个块，就可以整个块跳，不然直接暴力跳。暴力跳的次数和整块跳的次数都是小于等于 \sqrt n 次。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,len=300;
vector<int> v_d[N];
struct {int x,y,z;}c[N];
struct {int fa,maxx;}to_next[N];
int n,to_fa[N],f[N][25],d[N],pos[N];
vector<int> v[N];
void dfs(int x,int fa){
    d[x]=d[fa]+1;
    f[x][0]=fa;
    //LCA
    for(int i=1;i<=20&&f[x][i-1]!=0;i++) f[x][i]=f[f[x][i-1]][i-1];
    v_d[d[x]].push_back(x);//按照层数储存，便于分块
    for(int i=0;i<v[x].size();i++) if(v[x][i]!=fa) dfs(v[x][i],x);
}
int LCA(int x,int y){
    if(d[x]<d[y]) swap(x,y);
    for(int i=20;i>=0;i--)if(d[f[x][i]]>=d[y]) x=f[x][i];
    if(x==y) return x;
    for(int i=20;i>=0;i--)if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    return f[x][0];
}
// 处理 x 到它祖先里面最近的块不同的点之间的最大值
void solve(int x){
    if(x==1) return ;
    int fa=x,maxx=0;
    while(pos[fa]==pos[x])maxx=max(maxx,to_fa[fa]),fa=f[fa][0];
    to_next[x].fa=fa;//记录整块会跳到哪一个点
    to_next[x].maxx=maxx;//记录路径上的最大值
}
int get_max(int x,int y){
    int fa=LCA(x,y),ans=0;
    while(pos[x]!=pos[fa])ans=max(ans,to_next[x].maxx),x=to_next[x].fa;
    while(x!=fa)ans=max(ans,to_fa[x]),x=f[x][0];
    //让 x 跳到 x,y 的最近公共祖先
    while(pos[y]!=pos[fa])ans=max(ans,to_next[y].maxx),y=to_next[y].fa;
    while(y!=fa)ans=max(ans,to_fa[y]),y=f[y][0];
    return ans;
}
bool vis[N];
// 快速更新同一个块里面的信息
void reset(int x){
    solve(x);
    //先把当前点更新好，然后把他的子节点中和他在同一块里的更新
    //因为最多有 len 个点，所以这个操作的时间复杂度是根号的
    queue<pair<int,int>> q;
    q.push({x,to_next[x].maxx});
    while(q.size()){
        int xx=q.front().first,z=q.front().second;
        vis[xx]=1;
        q.pop();
        for(int j=0;j<v[xx].size();j++){
            int i=v[xx][j];
            if(d[i]<d[xx]) continue;
            if(pos[i]==pos[x]){
                to_next[i].maxx=max(z,to_fa[i]);
                to_next[i].fa=to_next[x].fa;
                q.push(make_pair(i,to_next[i].maxx));
            }
        }
    }
}
signed main(){
    cin.tie(0)->sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<n;i++){
        cin>>c[i].x>>c[i].y>>c[i].z;
        v[c[i].x].push_back(c[i].y);
        v[c[i].y].push_back(c[i].x);
    }
    dfs(1,0);
    int cnt=len-1,point=1;
    for(int i=1;i<=n;i++){
        //记录每一个点向父亲连边的边权。
        if(d[c[i].x]<d[c[i].y]) to_fa[c[i].y]=c[i].z;
        else to_fa[c[i].x]=c[i].z;
        //把每一个点放到块上
        for(int j=0;j<v_d[i].size();j++){
            cnt++;
            pos[v_d[i][j]]=point;
            if(cnt>=len) cnt=0,point++;
        }
    }
    //初始化每一个点整块向上跳一次的终点和之间的最大值
    for(int k=2;k<=n;k++)
        for(int i=0;i<v_d[k].size();i++) 
            if(!vis[v_d[k][i]]) 
                reset(v_d[k][i]);
    string s;
    while(cin>>s){
        if(s=="DONE") return 0;
        int x,y,k;
        if(s=="CHANGE") {
            cin>>k>>x;
            c[k].z=x;
            //更新边权
            if(d[c[k].x]<d[c[k].y]) to_fa[c[k].y]=c[k].z;
            else to_fa[c[k].x]=c[k].z;
            //更新整块跳的最大值
            if(d[c[k].x]<d[c[k].y]) reset(c[k].y);
            else reset(c[k].x);
        }
        else {
            cin>>x>>y;
            cout<<get_max(x,y)<<"\n";
        }
    }
    return 0;
}