XCPC Notes

Appearance

发布时间：2024-02-05

五个概念 ​

  • 重儿子：儿子中最大size的节点
  • 轻儿子：除重儿子外的儿子
  • 重边：连接重儿子的边
  • 轻边：连接轻儿子的边
  • 重链：重儿子往上走到根节点或者轻儿子的边(亦可以是一个轻儿子)

题型 ​

对一棵树的路径进行大量的操作
树链剖分即将每条重链分出来 (O(logN)条)(O(logN)条)
将节点按照先重儿子的dfs序排好,用线段树维护每个区间(重链)的信息
总复杂度：O(log2N)总复杂度：O(log^2 N )

P3384 树链剖分模板 ​

cpp
struct node{
    ll l,r,add,sum;
} t[N<<2];
ll w[N],siz[N],id[N],nw[N],dep[N],top[N],par[N],son[N];
/*
w[i]是原来的值
siz[i]是树的大小
id[i]是dfs序编号
nw[i]是dfs序为i的值
dep[i]为高度
top[i]为当前i所在的重链的头部
par[i]为父节点
son[i]为重儿子
*/
ll n,m,r,mod;
vector<ll> adj[N];
void dfs1(int u,int fa){//预处理
    par[u]=fa;
    dep[u]=dep[fa]+1;
    siz[u]=1;
    for(auto v:adj[u]){
        if(v==fa)continue;
        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[son[u]]<siz[v])son[u]=v;
    }
}
int cnt=0;
void dfs2(int u,int t){//dfs序，重链头节点
    id[u]=++cnt;
    nw[cnt]=w[u];
    top[u]=t;
    if(!son[u])return;
    dfs2(son[u],t);
    for(auto v:adj[u]){
        if(v==par[u]||v==son[u])continue;
        dfs2(v,v);
    }
}
void pushup(int p){
    t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
}
void pushdown(int p){
    auto &u=t[p],&l=t[p<<1],&r=t[p<<1|1];
    l.sum+=u.add*(l.r-l.l+1);
    r.sum+=u.add*(r.r-r.l+1);
    l.add+=u.add;
    r.add+=u.add;
    u.add=0;
}
void build(int p,int l,int r){
    t[p]={l,r,0,nw[r]};
    if(l==r)return;
    int mid=l+r>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    pushup(p);
}
void modify(int p,int l,int r,int k){
    if(l<=t[p].l&&r>=t[p].r){
        t[p].add+=k;
        t[p].sum+=k*(t[p].r-t[p].l+1);
        return;
    }
    pushdown(p);
    int mid=t[p].l+t[p].r>>1;
    if(l<=mid)modify(p<<1,l,r,k);
    if(r>mid)modify(p<<1|1,l,r,k);
    pushup(p);
}
ll query(int p,int l,int r){
    if(l<=t[p].l&&r>=t[p].r)return t[p].sum;
    pushdown(p);
    ll res=0;
    int mid=t[p].l+t[p].r>>1;
    if(l<=mid)res+=query(p<<1,l,r);
    if(r>mid)res+=query(p<<1|1,l,r);
    return res;
}
void modify_path(int u,int v,int k){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        modify(1,id[top[u]],id[u],k);
        u=par[top[u]];
    }
    if(dep[u]<dep[v])swap(u,v);
    modify(1,id[v],id[u],k);
}
ll query_path(int u,int v){
    ll res=0;
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        res+=query(1,id[top[u]],id[u]);
        u=par[top[u]];
    }
    if(dep[u]<dep[v])swap(u,v);
    res+=query(1,id[v],id[u]);
    return res;    
}
void modify_tree(int u,int k){
    modify(1,id[u],id[u]+siz[u]-1,k);
}
ll query_tree(int u){
    return query(1,id[u],id[u]+siz[u]-1);
}
void solve(){
    cin>>n>>m>>r>>mod;
    for(int i=1;i<=n;i++)cin>>w[i];
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs1(r,0);
    dfs2(r,r);
    build(1,1,n);
    while(m--){
        int op,x,y,z;
        cin>>op>>x;
        if(op==1){
            cin>>y>>z;
            modify_path(x,y,z);
        }
        else if(op==2){
            cin>>y;
            cout<<query_path(x,y)%mod<<"\n";
        }
        else if(op==3){
            cin>>z;
            modify_tree(x,z);
        }
        else{
            cout<<query_tree(x)%mod<<"\n";
        }
    }
}

P2486 染色 ​

题目描述 ​

给定一棵 nn 个节点的无根树，共有 mm 个操作，操作分为两种：

  1. 将节点 aa 到节点 bb 的路径上的所有点（包括 aa 和 bb）都染成颜色 cc。
  2. 询问节点 aa 到节点 bb 的路径上的颜色段数量。

颜色段的定义是极长的连续相同颜色被认为是一段。例如 112221 由三段组成：11、222、1。

输入格式 ​

输入的第一行是用空格隔开的两个整数，分别代表树的节点个数 nn 和操作个数 mm。

第二行有 nn 个用空格隔开的整数，第 ii 个整数 wiw_i 代表结点 ii 的初始颜色。

第 33 到第 (n+1)(n + 1) 行，每行两个用空格隔开的整数 u,vu, v，代表树上存在一条连结节点 uu 和节点 vv 的边。

第 (n+2)(n + 2) 到第 (n+m+1)(n + m + 1) 行，每行描述一个操作，其格式为：

每行首先有一个字符 opop，代表本次操作的类型。

  • 若 opop 为 C，则代表本次操作是一次染色操作，在一个空格后有三个用空格隔开的整数 a,b,ca, b, c，代表将 aa 到 bb 的路径上所有点都染成颜色 cc。
  • 若 opop 为 Q，则代表本次操作是一次查询操作，在一个空格后有两个用空格隔开的整数 a,ba, b，表示查询 aa 到 bb 路径上的颜色段数量。

输出格式 ​

对于每次查询操作，输出一行一个整数代表答案。

样例 #1 ​

样例输入 #1 ​

6 5
2 2 1 2 1 1
1 2
1 3
2 4
2 5
2 6
Q 3 5
C 2 1 1
Q 3 5
C 5 1 2
Q 3 5

样例输出 #1 ​

3
1
2

提示 ​

数据规模与约定 ​

对于 100%100\% 的数据，1≤n,m≤1051 \leq n, m \leq 10^5，1≤wi,c≤1091 \leq w_i, c \leq 10^9，1≤a,b,u,v≤n1 \leq a, b, u, v \leq n，opop 一定为 C 或 Q，保证给出的图是一棵树。

除原数据外，还存在一组不计分的 hack 数据。

思路 ​

线段树维护信息，左颜色和右颜色，颜色总数，懒标记为是否涂色
难点：
这题重载运算符代替pushup方便后续计算
重链爬山法跳跃时，使用三个标记bool
g为0表示轮到L否则轮到R
lg表示L是否有跳跃过
rg表示R是否跳跃
定义线段的起始均为由深到浅，最后询问中间线段时，谁深度浅就翻转，判断合并即可

cpp
struct node{
    ll l,r,lc,rc,tag,sum;
    node operator+(const node&tmp){
        node ans;
        ans.l=l,ans.r=tmp.r;
        ans.lc=lc,ans.rc=tmp.rc;
        ans.sum=sum+tmp.sum-(rc==tmp.lc);
        ans.tag=0;
        return ans;
    }
} t[N<<2];
int w[N],siz[N],dep[N],par[N],son[N],top[N],id[N],nw[N],idx;
vector<int> adj[N];
void dfs1(int u,int fa){
    siz[u]=1;
    dep[u]=dep[fa]+1;
    par[u]=fa;
    for(auto v:adj[u]){
        if(v==fa)continue;
        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[son[u]]<siz[v])son[u]=v;
    }
}
void dfs2(int u,int t){
    top[u]=t;
    id[u]=++idx;
    nw[idx]=w[u];
    if(!son[u])return;
    dfs2(son[u],t);
    for(auto v:adj[u]){
        if(v==par[u]||v==son[u])continue;
        dfs2(v,v);
    }
}
void pushup(int p){
    t[p]=t[p<<1]+t[p<<1|1];
}
void pushdown(int p){
    auto &u=t[p],&l=t[p<<1],&r=t[p<<1|1];
    if(u.tag){
        l.sum=r.sum=1;
        l.lc=l.rc=r.lc=r.rc=l.tag=r.tag=u.tag;
        u.tag=0;
    }
}
void build(int p,int l,int r){
    t[p]={l,r,nw[l],nw[r],0,1};
    if(l==r)return;
    int mid=l+r>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    pushup(p);
}
void modify(int p,int l,int r,int k){
    if(l<=t[p].l&&r>=t[p].r){
        t[p].tag=t[p].lc=t[p].rc=k;
        t[p].sum=1;
        return;
    }
    pushdown(p);
    int mid=t[p].l+t[p].r>>1;
    if(l<=mid)modify(p<<1,l,r,k);
    if(r>mid)modify(p<<1|1,l,r,k);
    pushup(p);
}
node query(int p,int l,int r){
    if(l<=t[p].l&&r>=t[p].r)return t[p];
    pushdown(p);
    int mid=t[p].l+t[p].r>>1;
    if(l<=mid&&r>mid)return query(p<<1,l,r)+query(p<<1|1,l,r);
    if(l<=mid)return query(p<<1,l,r);
    if(r>mid)return query(p<<1|1,l,r);
}
void modify_path(int u,int v,int k){//不做改变
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        modify(1,id[top[u]],id[u],k);
        u=par[top[u]];
    }
    if(dep[u]<dep[v])swap(u,v);
    modify(1,id[v],id[u],k);
}
node query_path(int u,int v){
    node L,R;
    int g=0,lg=0,rg=0;
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v),g^=1;
        node res=query(1,id[top[u]],id[u]);
        if(res.r!=id[top[u]])swap(res.l,res.r),swap(res.lc,res.rc);
        u=par[top[u]];
        if(!g){
            if(!lg)L=res,lg=1;
            else L=L+res;
        }
        else{
            if(!rg)R=res,rg=1;
            else R=R+res;
        }
    }
    if(dep[u]<dep[v])swap(u,v),g^=1;
    node res=query(1,id[v],id[u]);
    if(!g){
        swap(L.lc,L.rc);
        if(lg&&rg)return R+res+L;
        if(lg)return res+L;
        if(rg)return R+res;
        return res;
    }
    swap(R.lc,R.rc);
    if(lg&&rg)return L+res+R;
    if(lg)return L+res;
    if(rg)return res+R;
    return res;
}
/*void modify_tree(int u,int k){
    modify(1,id[u],id[u]+siz[u]-1,k);
}
node query_tree(int u){
    return query(1,id[u],id[u]+siz[u]-1);
}*/
void solve(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>w[i];
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs1(1,0);
    dfs2(1,1);
    build(1,1,n);
    while(m--){
        char op;
        cin>>op;
        int x,y,z;
        if(op=='C'){
            cin>>x>>y>>z;
            modify_path(x,y,z);
        }
        else{
            cin>>x>>y;
            cout<<query_path(x,y).sum<<"\n";
        }
    }
}

[国家集训队] 旅游(边权转点权) ​

题目背景 ​

Ray 乐忠于旅游，这次他来到了 T 城。T 城是一个水上城市，一共有 nn 个景点，有些景点之间会用一座桥连接。为了方便游客到达每个景点但又为了节约成本，T 城的任意两个景点之间有且只有一条路径。换句话说， T 城中只有 n−1n-1 座桥。

Ray 发现，有些桥上可以看到美丽的景色，让人心情愉悦，但有些桥狭窄泥泞，令人烦躁。于是，他给每座桥定义一个愉悦度 ww，也就是说，Ray 经过这座桥会增加 ww 的愉悦度，这或许是正的也可能是负的。有时，Ray 看待同一座桥的心情也会发生改变。

现在，Ray 想让你帮他计算从 uu 景点到 vv 景点能获得的总愉悦度。有时，他还想知道某段路上最美丽的桥所提供的最大愉悦度，或是某段路上最糟糕的一座桥提供的最低愉悦度。

题目描述 ​

给定一棵 nn 个节点的树，边带权，编号 0∼n−10 \sim n-1，需要支持五种操作：

  • C i w 将输入的第 ii 条边权值改为 ww；
  • N u v 将 u,vu,v 节点之间的边权都变为相反数；
  • SUM u v 询问 u,vu,v 节点之间边权和；
  • MAX u v 询问 u,vu,v 节点之间边权最大值；
  • MIN u v 询问 u,vu,v 节点之间边权最小值。

保证任意时刻所有边的权值都在 [−1000,1000][-1000,1000] 内。

输入格式 ​

第一行一个正整数 nn，表示节点个数。
接下来 n−1n-1 行，每行三个整数 u,v,wu,v,w，表示 u,vu,v 之间有一条权值为 ww 的边，描述这棵树。
然后一行一个正整数 mm，表示操作数。
接下来 mm 行，每行表示一个操作。

输出格式 ​

对于每一个询问操作，输出一行一个整数表示答案。

样例 #1 ​

样例输入 #1 ​

3
0 1 1
1 2 2
8
SUM 0 2
MAX 0 2
N 0 1
SUM 0 2
MIN 0 2
C 1 3
SUM 0 2
MAX 0 2

样例输出 #1 ​

3
2
1
-1
5
3

提示 ​

【数据范围】

对于 100%100\% 的数据，1≤n,m≤2×1051\le n,m \le 2\times 10^5。

2020.02.04 修正了一点数据的错误
2020.03.14 加入了一组 hack 数据
2020.11.26 加入了一组 hack 数据 By @_Leaving

思路 ​

dfs序边权转点权，儿子记录边权信息
路径查询和修改时，上节点为原上节点的子节点(特别地，u==v不用计算)
修改单条边时，修改深度较深的点权
维护相反数：sum,mx,mn取反,swap(mx,mn)

cpp
struct node{
    ll l,r,add,sum,mx,mn;
} t[N<<2];
ll w[N],siz[N],id[N],nw[N],dep[N],top[N],par[N],son[N];
vector<PII> adj[N];
void dfs1(int u,int fa){//预处理
    par[u]=fa;
    dep[u]=dep[fa]+1;
    siz[u]=1;
    for(auto [v,c]:adj[u]){
        if(v==fa)continue;
        w[v]=c;
        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[son[u]]<siz[v])son[u]=v;
    }
}
int cnt=0;
void dfs2(int u,int t){//dfs序，重链头节点
    id[u]=++cnt;
    nw[cnt]=w[u];
    top[u]=t;
    if(!son[u])return;
    dfs2(son[u],t);
    for(auto [v,c]:adj[u]){
        if(v==par[u]||v==son[u])continue;
        dfs2(v,v);
    }
}
void pushup(int p){
    t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
    t[p].mx=max(t[p<<1].mx,t[p<<1|1].mx);
    t[p].mn=min(t[p<<1].mn,t[p<<1|1].mn);
}
void pushdown(int p){
    auto &u=t[p],&l=t[p<<1],&r=t[p<<1|1];
    if(u.add){
        l.sum=-l.sum;
        r.sum=-r.sum;
        l.add^=1;
        r.add^=1;
        l.mx=-l.mx,l.mn=-l.mn,swap(l.mx,l.mn);
        r.mx=-r.mx,r.mn=-r.mn,swap(r.mx,r.mn);
        u.add=0;
    }
}
void build(int p,int l,int r){
    t[p]={l,r,0,nw[r],nw[r],nw[r]};
    if(l==r)return;
    int mid=l+r>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    pushup(p);
}
void modify(int p,int x,int k){
    if(t[p].l==t[p].r){
        t[p].sum=t[p].mx=t[p].mn=k;
        t[p].add=0;
        return;
    }
    pushdown(p);
    int mid=t[p].l+t[p].r>>1;
    if(x<=mid)modify(p<<1,x,k);
    if(x>mid)modify(p<<1|1,x,k);
    pushup(p);   
}
void modify_rev(int p,int l,int r){
    if(l<=t[p].l&&r>=t[p].r){
        t[p].sum=-t[p].sum;
        t[p].mx=-t[p].mx;
        t[p].mn=-t[p].mn;
        swap(t[p].mx,t[p].mn);
        t[p].add^=1;
        return;
    }
    pushdown(p);
    int mid=t[p].l+t[p].r>>1;
    if(l<=mid)modify_rev(p<<1,l,r);
    if(r>mid)modify_rev(p<<1|1,l,r);
    pushup(p);
}
ll query(int p,int l,int r){
    if(l<=t[p].l&&r>=t[p].r)return t[p].sum;
    pushdown(p);
    ll res=0;
    int mid=t[p].l+t[p].r>>1;
    if(l<=mid)res+=query(p<<1,l,r);
    if(r>mid)res+=query(p<<1|1,l,r);
    return res;
}
ll query_mx(int p,int l,int r){
    if(l<=t[p].l&&r>=t[p].r)return t[p].mx;
    pushdown(p);
    ll res=-INF;
    int mid=t[p].l+t[p].r>>1;
    if(l<=mid)res=max(res,query_mx(p<<1,l,r));
    if(r>mid)res=max(res,query_mx(p<<1|1,l,r));
    return res;
}
ll query_mn(int p,int l,int r){
    if(l<=t[p].l&&r>=t[p].r)return t[p].mn;
    pushdown(p);
    ll res=INF;
    int mid=t[p].l+t[p].r>>1;
    if(l<=mid)res=min(res,query_mn(p<<1,l,r));
    if(r>mid)res=min(res,query_mn(p<<1|1,l,r));
    return res;
}
void modify_path(int u,int v){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        modify_rev(1,id[top[u]],id[u]);
        u=par[top[u]];
    }
    if(dep[u]<dep[v])swap(u,v);
    if(u!=v)modify_rev(1,id[v]+1,id[u]);
}
ll query_path(int u,int v){
    ll res=0;
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        res+=query(1,id[top[u]],id[u]);
        u=par[top[u]];
    }
    if(dep[u]<dep[v])swap(u,v);
    if(u!=v)res+=query(1,id[v]+1,id[u]);
    return res;    
}
ll query_path_mx(int u,int v){
    ll res=-INF;
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        res=max(res,query_mx(1,id[top[u]],id[u]));
        u=par[top[u]];
    }
    if(dep[u]<dep[v])swap(u,v);
    if(u!=v)res=max(res,query_mx(1,id[v]+1,id[u]));
    return res;    
}
ll query_path_mn(int u,int v){
    ll res=INF;
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        res=min(res,query_mn(1,id[top[u]],id[u]));
        u=par[top[u]];
    }
    if(dep[u]<dep[v])swap(u,v);
    if(u!=v)res=min(res,query_mn(1,id[v]+1,id[u]));
    return res;    
}
struct edge{
    int u,v,c;
};
void solve(){
    int n;
    cin>>n;
    vector<edge> a(n+1);
    for(int i=1;i<n;i++){
        auto &[u,v,c]=a[i];
        cin>>u>>v>>c;
        u++;v++;
        adj[u].push_back({v,c});
        adj[v].push_back({u,c});
    }
    dfs1(1,0);
    dfs2(1,1);
    build(1,1,n);
    int q;
    cin>>q;
    //cout<<query_path(1,3)<<"\n";
    while(q--){
        string op;
        int x,y;
        cin>>op>>x>>y;
        x++;y++;
        if(op=="SUM")cout<<query_path(x,y)<<"\n";
        else if(op=="MAX")cout<<query_path_mx(x,y)<<"\n";
        else if(op=="MIN")cout<<query_path_mn(x,y)<<"\n";
        else if(op=="C"){
            x--;y--;
            auto [u,v,c]=a[x];
            if(dep[u]<dep[v])modify(1,id[v],y);
            else modify(1,id[u],y);
        }
        else{
            modify_path(x,y);
        }
    }
}

最短距离（基环树树剖） ​

题目描述 ​

给出一个 nn 个点 nn 条边的无向连通图。

你需要支持两种操作：

  1. 修改 第 xx 条边的长度为 yy ；

  2. 查询 点 xx 到点 yy 的最短距离。

共有 mm 次操作。

输入格式 ​

输入共 n+m+1n+m+1 行：

第 11 行，包含两个正整数 n,mn,m，表示点数即边数，操作次数。

第 22 行到第 n+1n+1 行，每行包含三个正整数 x,y,zx,y,z，表示 xx 与 yy 间有一条长度为 zz 的边。

第 n+2n+2 到 n+m+1n+m+1 行，每行包含三个正整数 op,x,yop,x,y，表示操作种类，操作的参数（含义见【题目描述】）。

输出格式 ​

对于每次操作 22 输出查询的结果。

样例 #1 ​

样例输入 #1 ​

4 5
1 2 11
1 3 12
2 3 13
1 4 15
2 2 3
1 2 1
2 2 3
2 2 4
2 3 4

样例输出 #1 ​

13
12
26
16

提示 ​

Luogu

对于 100%100\% 的数据，保证 z∈[0,5000]z\in [0,5000]。

思路 ​

  • 利用并查集将多余的一条边挑出来，剩下n-1条边连边
  • 查询时，取以下三个值的最小值
    • dis(x,y)dis(x,y)
    • dis(x,u)+w+dis(v,y)dis(x,u)+w+dis(v,y)
    • dis(x,v)+w+dis(u,y)dis(x,v)+w+dis(u,y)
cpp
struct node{
    int l,r,sum;
} t[N<<2];
vector<PII> adj[N];
int siz[N],son[N],par[N],dep[N],top[N],w[N],nw[N],id[N];
void dfs1(int u,int fa){
    dep[u]=dep[fa]+1;
    par[u]=fa;
    siz[u]=1;
    for(auto [v,c]:adj[u]){
        if(v==fa)continue;
        w[v]=c;
        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[son[u]]<siz[v])son[u]=v;
    }
}
int idx=0;
void dfs2(int u,int t){
    id[u]=++idx;
    nw[idx]=w[u];
    top[u]=t;
    if(!son[u])return;
    dfs2(son[u],t);
    for(auto [v,c]:adj[u]){
        if(v==par[u]||v==son[u])continue;
        dfs2(v,v);
    }
}
void pushup(int p){
    t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
}
void build(int p,int l,int r){
    t[p]={l,r,nw[r]};
    if(l==r)return;
    int mid=l+r>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    pushup(p);
}
void modify_change(int p,int l,int r,int k){
    if(l<=t[p].l&&r>=t[p].r){
        t[p].sum=k;
        return;
    }
    //pushdown(p);
    int mid=t[p].l+t[p].r>>1;
    if(l<=mid)modify_change(p<<1,l,r,k);
    if(r>mid)modify_change(p<<1|1,l,r,k);
    pushup(p);
}
ll query(int p,int l,int r){
    if(l<=t[p].l&&r>=t[p].r)return t[p].sum;
    //pushdown(p);
    int mid=t[p].l+t[p].r>>1;
    ll res=0;
    if(l<=mid)res+=query(p<<1,l,r);
    if(r>mid)res+=query(p<<1|1,l,r);
    return res;
}
ll query_path(int u,int v){
    ll res=0;
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        res+=query(1,id[top[u]],id[u]);
        u=par[top[u]];
    }
    if(dep[u]<dep[v])swap(u,v);
    if(u!=v)res+=query(1,id[v]+1,id[u]);
    return res;
}
struct edge{
    int u,v,c;
};
int Set[N];
int find(int x){
    return Set[x]==x?x:Set[x]=find(Set[x]);
}
void solve(){
    int n,m;
    cin>>n>>m;
    vector<edge> e(n+1);
    int pos;
    for(int i=1;i<=n;i++)Set[i]=i;
    for(int i=1;i<=n;i++){
        auto &[u,v,c]=e[i];
        cin>>u>>v>>c;
        int fu=find(u),fv=find(v);
        if(fu==fv){
            pos=i;
            continue;
        }
        Set[fu]=fv;
        adj[u].push_back({v,c});
        adj[v].push_back({u,c});
    }
    dfs1(1,0);
    dfs2(1,1);
    build(1,1,n);
    while(m--){
        int op,x,y;
        cin>>op>>x>>y;
        if(op==1){
            if(x==pos)e[x].c=y;
            else{
                auto [u,v,c]=e[x];
                if(id[u]<id[v])modify_change(1,id[v],id[v],y);
                else modify_change(1,id[u],id[u],y);
            }
        }
        else{
            ll dis1=query_path(x,y);
            auto [u,v,c]=e[pos];
            ll dis2=query_path(x,u)+query_path(v,y)+c;
            ll dis3=query_path(x,v)+query_path(u,y)+c;
            cout<<min({dis1,dis2,dis3})<<"\n";
        }
    }
}

[LNOI2014] LCA(差分+树剖) ​

题目描述 ​

给出一个 nn 个节点的有根树（编号为 00 到 n−1n-1，根节点为 00）。

一个点的深度定义为这个节点到根的距离 +1+1。

设 dep[i]dep[i] 表示点 ii 的深度，LCA⁡(i,j)\operatorname{LCA}(i, j) 表示 ii 与 jj 的最近公共祖先。

有 mm 次询问，每次询问给出 l,r,zl, r, z，求 ∑i=lrdep[LCA⁡(i,z)]\sum_{i=l}^r dep[\operatorname{LCA}(i,z)] 。

输入格式 ​

第一行 22 个整数，n,mn, m。

接下来 n−1n-1 行，分别表示点 11 到点 n−1n-1 的父节点编号。

接下来 mm 行，每行 33 个整数，l,r,zl, r, z。

输出格式 ​

输出 qq 行，每行表示一个询问的答案。每个答案对 201314201314 取模输出。

样例 #1 ​

样例输入 #1 ​

5 2
0
0
1
1
1 4 3
1 4 2

样例输出 #1 ​

8
5

提示 ​

对于 20%20\% 的数据，n≤10000,m≤10000n\le 10000,m\le 10000；

对于 40%40\% 的数据，n≤20000,m≤20000n\le 20000,m\le 20000；

对于 60%60\% 的数据，n≤30000,m≤30000n\le 30000,m\le 30000；

对于 80%80\% 的数据，n≤40000,m≤40000n\le 40000,m\le 40000；

对于 100%100\% 的数据，1≤n≤50000,1≤m≤500001\le n\le 50000,1\le m\le 50000。

思路 ​

  • 每个询问[l,r]可以分解为[1,r]−[1,l−1]每个询问[l,r]可以分解为[1,r]-[1,l-1]
  • 深度可以看成节点到根的路径加1,预处理出来所有的节点,询问lca(i,z)即求1-z路径和
  • 为了防止计算 [l,r][l,r] 外的点,将l,r分别存储起来排序，然后可以从小到大添加i到节点的路径,单独计算单个点和z的答案,在最后再相减
cpp
struct node{
    int l,r,add,sum;
} t[N<<2];
vector<int> adj[N];
int siz[N],son[N],par[N],dep[N],top[N],w[N],nw[N],id[N];
void dfs1(int u,int fa){
    dep[u]=dep[fa]+1;
    par[u]=fa;
    siz[u]=1;
    for(auto v:adj[u]){
        if(v==fa)continue;
        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[son[u]]<siz[v])son[u]=v;
    }
}
int idx=0;
void dfs2(int u,int t){
    id[u]=++idx;
    nw[idx]=w[u];
    top[u]=t;
    if(!son[u])return;
    dfs2(son[u],t);
    for(auto v:adj[u]){
        if(v==par[u]||v==son[u])continue;
        dfs2(v,v);
    }
}
void pushup(int p){
    t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
}
void pushdown(int p){
    auto &u=t[p],&l=t[p<<1],&r=t[p<<1|1];
    if(u.add){
        l.sum+=u.add*(l.r-l.l+1);
        r.sum+=u.add*(r.r-r.l+1);
        l.add+=u.add;
        r.add+=u.add;
        u.add=0;
    }
}
void build(int p,int l,int r){
    t[p]={l,r,0,nw[r]};
    if(l==r)return;
    int mid=l+r>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    pushup(p);
}
void modify(int p,int l,int r,int k){
    if(l<=t[p].l&&r>=t[p].r){
        t[p].sum+=k*(t[p].r-t[p].l+1);
        t[p].add+=k;
        return;
    }
    pushdown(p);
    int mid=t[p].l+t[p].r>>1;
    if(l<=mid)modify(p<<1,l,r,k);
    if(r>mid)modify(p<<1|1,l,r,k);
    pushup(p);
}
ll query(int p,int l,int r){
    if(l<=t[p].l&&r>=t[p].r)return t[p].sum;
    pushdown(p);
    int mid=t[p].l+t[p].r>>1;
    ll res=0;
    if(l<=mid)res+=query(p<<1,l,r);
    if(r>mid)res+=query(p<<1|1,l,r);
    return res;
}
void modify_path(int u,int v,int k){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        modify(1,id[top[u]],id[u],k);
        u=par[top[u]];
    }
    if(dep[u]<dep[v])swap(u,v);
    modify(1,id[v],id[u],k);
}
ll query_path(int u,int v){
    ll res=0;
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        res+=query(1,id[top[u]],id[u]);
        u=par[top[u]];
    }
    if(dep[u]<dep[v])swap(u,v);
    res+=query(1,id[v],id[u]);
    return res;
}
struct Q{
    int r,z,id;
    bool flag;
    bool operator<(const Q&tmp)const{
        return r<tmp.r;
    }
};
void solve(){
    int n,m;
    cin>>n>>m;
    for(int i=2;i<=n;i++){
        int u;
        cin>>u;
        u++;
        adj[u].push_back(i);
        adj[i].push_back(u);
    }
    dfs1(1,0);
    dfs2(1,1);
    build(1,1,n);
    vector<Q> q;
    vector<int> ans(m);
    for(int i=0;i<m;i++){
        int l,r,z;
        cin>>l>>r>>z;
        r++;z++;
        q.push_back({l,z,i,0});
        q.push_back({r,z,i,1});
    }
    sort(q.begin(),q.end());
    int R=0;
    for(int i=0;i<q.size();i++){
        auto [r,z,id,flag]=q[i];
        for(int j=R+1;j<=r;j++)modify_path(1,j,1);
        R=r;
        ans[id]+=(flag?1:-1)*query_path(1,z);
    }
    for(auto it:ans)cout<<it%mod<<"\n";
}

长链剖分 ​

CF1009 Dominant Indices(模板) ​

题意 ​

给定一棵树,对于每个点找出一个距离k,使得在该子树下与该点距离为k的点数最多

思路 ​

  • f[u][i]表示u节点距离为i的点数, fu,i=∑fv,i−1f_{u,i}= \sum f_{v,i-1}
  • 直接转移为 O(n2)O(n^2)

考虑优化,长链剖分,类似于启发式合并,定义深度最大的点为son[u]

  • 对于一条长链上的点使用同一块内存空间f[son[u]]=f[u]+1即向右移一次(假设u的第二维的头为1,向右移一位son[u]的第二维的头变成2,因此更新f[son[u]][i]即为更新f[u][i+1])
  • 除重儿子外的轻儿子,暴力转移(转移次数为dep[v]),总深度为n因此总复杂度为O(n)O(n)
cpp
int dep[N],son[N],ans[N];
int buf[N],*f[N],*it=buf;
vector<int> adj[N];
void dfs1(int u,int fa){
    for(auto v:adj[u]){
        if(v==fa)continue;
        dfs1(v,u);
        if(dep[son[u]]<dep[v])son[u]=v;
    }
    dep[u]=dep[son[u]]+1;
}
void dfs2(int u,int fa){
    f[u][0]=1;
    if(!son[u])return;
    f[son[u]]=f[u]+1;
    dfs2(son[u],u);
    ans[u]=ans[son[u]]+1;
    if(f[u][ans[u]]==1)ans[u]=0;
    for(auto v:adj[u]){
        if(v==fa||v==son[u])continue;
        f[v]=it,it+=dep[v];
        dfs2(v,u);
        for(int i=1;i<=dep[v];i++){
            f[u][i]+=f[v][i-1];
            if(f[u][i]>f[u][ans[u]]||(f[u][i]==f[u][ans[u]]&&i<ans[u]))ans[u]=i;
        }
    }
}
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs1(1,0);
    f[1]=it,it+=dep[1];
    dfs2(1,0);
    for(int i=1;i<=n;i++)cout<<ans[i]<<"\n";
}

P3565 [POI2014] HOT-Hotels(长链剖分+树形dp) ​

题意：
给定一棵树，在树上选3个点，要求两两距离相等，求方案数。 思路：

  • 定义fu,i表示以u为根的子树，与点u距离为i的点数定义f_{u,i}表示以u为根的子树，与点u距离为i的点数
  • 定义gu,i表示以u为根的子树，满足以下条件的点对数定义g_{u,i}表示以u为根的子树，满足以下条件的点对数
    • 设点对(x,y)，他们到lca(x,y)的距离为d，lca(x,y)到点u的距离为d−i设点对(x,y)，他们到lca(x,y)的距离为d，lca(x,y)到点u的距离为d-i
  • 更新答案
    • 在之前的分支选择两个点，在当前分支选择一个点
      ans+=gu,i+1×fv,ians+=g_{u,i+1} \times f_{v,i}
    • 在之前分支选一个点，在当前分支选两个点
      ans+=fu,i−1×gv,ians+=f_{u,i-1} \times g_{v,i}
  • 更新f数组
    • fu,i+1+=fv,if_{u,i+1}+=f_{v,i}
  • 更新g数组
    • gu,i−1+=gv,ig_{u,i-1}+=g_{v,i}
    • gu,i+1+=fu,i+1×fv,i(此时d的值为d=i+1)g_{u,i+1}+=f_{u,i+1} \times f_{v,i} (此时d的值为d=i+1)
  • 注意事项：采用指针赋值，g数组传给重儿子时指针是向前移的，这样就可能会遍历到不是当前领域的数，因此赋值需要给每条长链两倍空间
cpp
vector<int> adj[N];
ll buf[N<<2];
ll dep[N],son[N],*f[N],*g[N],*id=buf;
void dfs1(int u,int fa){
    for(auto v:adj[u]){
        if(v==fa)continue;
        dfs1(v,u);
        if(dep[v]>dep[son[u]])son[u]=v;
    }
    dep[u]=dep[son[u]]+1;
}
ll ans;
void dfs2(int u,int fa){
    if(son[u]){
        f[son[u]]=f[u]+1;
        g[son[u]]=g[u]-1;
        dfs2(son[u],u);
    }
    f[u][0]=1;
    ans+=g[u][0];
    for(auto v:adj[u]){
        if(v==fa||v==son[u])continue;
        f[v]=id,id+=dep[v]+10;
        g[v]=id,id+=dep[v]+10;
        dfs2(v,u);
        for(int i=0;i<dep[v];i++){
            if(i)ans+=f[u][i-1]*g[v][i];
            ans+=g[u][i+1]*f[v][i];
        }
        for(int i=0;i<dep[v];i++){
            g[u][i+1]+=f[u][i+1]*f[v][i];
            if(i)g[u][i-1]+=g[v][i];
            f[u][i+1]+=f[v][i];
        }
    }
}
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs1(1,0);
    f[1]=id,id+=dep[1]+10;
    g[1]=id,id+=dep[1]+10;
    dfs2(1,0);
    cout<<ans<<"\n";
}

Wenwei Lin · 2022 — 2025