ZR 集训 Day5 – 树上信息维护

ooliver 发布于 9 小时前 71 次阅读 OI

AI 摘要

树上问题难？长链剖分让重儿子信息继承如丝般顺滑，暴力合并竟也是线性！点分治以重心为根，让树深对数级，路径查询不再恐惧。还有长剖优化 DP，精妙消除冗余计算。ZR 集训 Day5，解锁树上信息维护的高效秘诀！

ZR 集训 Day5 - 树上信息维护

CF1009F Dominant Indices

长链剖分模板题，和重链剖分一样，只不过把重儿子的定义换成了深度最大的儿子。对于一点的深度的定义，是这个点与这个点子树内叶子节点距离的最大值加一。

当 DFS 至一个点时，我们用常数的复杂度将其重儿子的 DP 值转移给它，并暴力地将其他儿子合并过来。因为每个点只会在一条链中被暴力合并，所以复杂度是线性的。

代码：

C++
#include<bits/stdc++.h>
using namespace std;
 
const int N=1e6+5;
int n;
int dep[N],son[N],fa[N],ans[N];
vector<int> t[N],dp[N];
 
void dfs1(int u,int f){
    fa[u]=f;
    for(int v:t[u]){
        if(v==f) continue;
        dfs1(v,u);
        if(dep[v]>dep[son[u]]) son[u]=v;
    }
    dep[u]=dep[son[u]]+1;
}
 
void dfs2(int u){
    if(son[u]){
        dfs2(son[u]);
        swap(dp[son[u]],dp[u]);
        ans[u]=ans[son[u]]+1;
    }
    dp[u].push_back(1);
    for(int v:t[u]){
        if(v==fa[u]||v==son[u]) continue;
        dfs2(v);
        for(int i=0;i<dep[v];i++){
            dp[u][dep[u]-(i+1)-1]+=dp[v][dep[v]-i-1];
            if(dp[u][dep[u]-(i+1)-1]>dp[u][dep[u]-ans[u]-1]||(dp[u][dep[u]-(i+1)-1]==dp[u][dep[u]-ans[u]-1]&&i+1<ans[u])) ans[u]=i+1;
        }
    }
    if(dp[u][dep[u]-ans[u]-1]<=1) ans[u]=0;
}
 
signed main(){
    cin>>n;
    for(int i=1,u,v;i<n;i++){
        cin>>u>>v;
        t[u].push_back(v);
        t[v].push_back(u);
    }
    dfs1(1,0);
    dfs2(1);
    for(int i=1;i<=n;i++) cout<<ans[i]<<"\n";
    return 0;
}

P3806 【模板】点分治

点分治模板。

点分治的核心是以当前递归子树的重心为根进行递归、操作，这样树的深度最大为 $\log$ 级别，就可以对经过中心的链进行暴力处理。

在这道题中，我们要求出 $m$ 次询问：树上是否存在树上距离为 $k$ 的点对。可以用一个桶来维护。新访问一个子树的链时，先通过桶统计之前子树有没有符合条件的链，再把当前子树的链长度添加到桶中。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N=1e4+5;
const int K=1e7+5;
int n,m,rt,sum,tot,ptot;
int siz[N],f[N],vis[N],qry[105],ans[105],q[N],p[N];
bool jdg[K];
struct node{int v,w;};
vector<node> t[N];

void getrt(int u,int fa){
    siz[u]=1,f[u]=0;
    for(node x:t[u]){
        int v=x.v;
        if(v==fa||vis[v]) continue;
        getrt(v,u);
        siz[u]+=siz[v];
        f[u]=max(f[u],siz[v]);
    }
    f[u]=max(f[u],sum-siz[u]);
    if(f[u]<f[rt]) rt=u;
}

void getdis(int u,int fa,int dis){
    if(dis>1e7) return;
    p[++ptot]=dis;
    for(node x:t[u]){
        int v=x.v,w=x.w;
        if(v==fa||vis[v]) continue;
        getdis(v,u,dis+w);
    }
}

void cal(int u){
    tot=0,q[++tot]=0,jdg[0]=1;
    for(node x:t[u]){
        int v=x.v,w=x.w;
        if(vis[v]) continue;
        ptot=0;
        getdis(v,u,w);
        for(int i=1;i<=ptot;i++){
            for(int j=1;j<=m;j++){
                if(qry[j]>=p[i]&&jdg[qry[j]-p[i]]) ans[j]=1;
            }
        }
        for(int i=1;i<=ptot;i++){
            q[++tot]=p[i];
            jdg[p[i]]=1;
        }
    }
    for(int i=1;i<=tot;i++) jdg[q[i]]=0;
}

void solve(int u){
    vis[u]=1;
    cal(u);
    for(node x:t[u]){
        int v=x.v;
        if(vis[v]) continue;
        sum=siz[v],rt=0,f[0]=1e9;
        getrt(v,0);
        solve(rt);
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<n;i++){
        int u,v,w;
        cin>>u>>v>>w;
        t[u].push_back({v,w});
        t[v].push_back({u,w});
    }
    for(int i=1;i<=m;i++) cin>>qry[i];
    sum=n,rt=0,f[0]=1e9;
    getrt(1,0);
    solve(rt);
    for(int i=1;i<=m;i++) cout<<(ans[i]?"AYE\n":"NAY\n");
    return 0;
}

P5351 Ruri Loves Maschera

简化题意：求出树上所有边的数量在 $[L,R]$ 区间内的链上边权最大值之和。

用点分治求出以重心为根的所有链，我们按魔法值从小到大排序，那扫到当前链的魔法值就应该是产生贡献的魔法值最大值，用一个树状数组维护之前链的长度，查询符合条件的区间即可。

这里相同子树内的链可能会产生错误的贡献，所以一开始在遍历子节点时就把这个贡献减掉就行。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define lowbit(x) x&-x
const int N=1e5+5;

int n,l,r,rt,sum,ans,idx,idx1;
int siz[N],f[N],vis[N];
struct node{
    int v,w;
    bool operator<(const node &b)const{
        return v<b.v;
    }
}p[N],p1[N];
vector<node> t[N];

struct BIT{
    int tree[N];
    vector<node> dif;
    void add(int x,int k){
        x++;
        for(int i=x;i<N;i+=lowbit(i)) tree[i]+=k;
        dif.push_back({x,k });
    }
    int qry(int x){
        x++;
        if(x<=0) return 0;
        int res=0;
        for(int i=x;i>0;i-=lowbit(i)) res+=tree[i];
        return res;
    }
    void clear(){
        for(node x:dif) for(int i=x.v;i<N;i+=lowbit(i)) tree[i]-=x.w;
        dif.clear();
    }
}bit;

void getrt(int u,int fa){
    siz[u]=1,f[u]=0;
    for(node x:t[u]){
        int v=x.v;
        if(v==fa||vis[v]) continue;
        getrt(v,u);
        siz[u]+=siz[v];
        f[u]=max(f[u],siz[v]);
    }
    f[u]=max(f[u],sum-siz[u]);
    if(f[u]<f[rt]) rt=u;
}

void getdis(int u,int fa,int mx,int len){
    p[++idx]={mx,len};
    p1[++idx1]={mx,len};
    for(node x:t[u]){
        int v=x.v,w=x.w;
        if(v==fa||vis[v]) continue;
        getdis(v,u,max(mx,w),len+1);
    }
}

void getsiz(int u,int fa){
    siz[u]=1;
    for(node x:t[u]){
        int v=x.v;
        if(v==fa||vis[v]) continue;
        getsiz(v,u);
        siz[u]+=siz[v];
    }
}

void cal(int u){
    idx=0,p[++idx]={0,0};
    for(node x:t[u]){
        idx1=0;
        int v=x.v,w=x.w;
        if(vis[v]) continue;
        getdis(v,u,w,1);
        sort(p1+1,p1+1+idx1);
        for(int i=1;i<=idx1;i++){
            ans-=(bit.qry(r-p1[i].w)-bit.qry(l-p1[i].w-1))*p1[i].v;
            bit.add(p1[i].w,1);
        }
        bit.clear();
    }
    sort(p+1,p+1+idx);
    for(int i=1;i<=idx;i++){
        ans+=(bit.qry(r-p[i].w)-bit.qry(l-p[i].w-1))*p[i].v;
        bit.add(p[i].w,1);
    }
    bit.clear();
}

void solve(int u){
    vis[u]=1;
    cal(u);
    for(node x:t[u]){
        int v=x.v;
        if(vis[v]) continue;
        getsiz(v,u);
        sum=siz[v],rt=0,f[0]=1e9;
        getrt(v,0);
        solve(rt);
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>l>>r;
    for(int i=1;i<n;i++){
        int u,v,w;
        cin>>u>>v>>w;
        t[u].push_back({v,w});
        t[v].push_back({u,w});
    }
    sum=n,rt=0,f[0]=1e9;
    getrt(1,0);
    solve(rt);
    cout<<ans*2;
    return 0;
}

P5904 [POI 2014] HOT-Hotels 加强版

长链剖分优化 DP。

设 $a_{i,j}$ 表示点 $i$ 子树内距离它为 $j$ 的点的个数， $b_{i,j}$ 表示 $i$ 字树内满足两点距离其 LCA 相等、并且从 LCA 向上找同样距离的祖先，该祖先也是距离点 $i$ 为 $j$ 的祖先的无序点对的个数。

可以得到答案统计与状态转移式子：

$$
\begin{aligned}
ans&=\sum_{u} (b_{u,0}+\sum_{x,y\in son(u),x\not =y} \sum_i a_{x,i-1}*b_{y,i+1}) \\
a_{u,i}&=\sum_{v\in son(u)} a_{v,i-1} \\
b_{u,i}&=\sum_{v\in son(u)} b_{v,i+1} + \sum_{x,y\in son(u),x\not =y} a_{x,i-1}*a_{y,i-1}) \\
\end{aligned}
$$

发现以上信息都可以用长链剖分优化。

代码：

C++
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=1e5+5;
int n,dep[N],son[N],fa[N];
vector<int> t[N];
ll *f[N],*g[N],pool[N<<3],*now=pool,ans;

void dfs1(int u,int f){
    fa[u]=f;
    for(int v:t[u]){
        if(v==f)continue;
        dfs1(v,u);
        if(dep[v]>dep[son[u]]) son[u]=v;
    }
    dep[u]=dep[son[u]]+1;
}

void dfs2(int u){
    if(son[u]){
        f[son[u]]=f[u]+1;
        g[son[u]]=g[u]-1;
        dfs2(son[u]);
    }
    f[u][0]=1;
    ans+=g[u][0];
    for(int v:t[u]){
        if(v==fa[u]||v==son[u]) continue;
        f[v]=now,now+=dep[v]<<1;
        g[v]=now,now+=dep[v]<<1;
        dfs2(v);
        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];
        }
    }
}

int main(){
    cin>>n;
    for(int i=1,u,v;i<n;i++){
        cin>>u>>v;
        t[u].push_back(v);
        t[v].push_back(u);
    }
    dfs1(1,0);
    f[1]=now,now+=dep[1]<<1;
    g[1]=now,now+=dep[1]<<1;
    dfs2(1);
    cout<<ans;
    return 0;
}