树上用最少点覆盖路径 & 树上选出最多不相交路径

等价性

问题 1：给定一棵树，和 $m$ 条路径，求最少选几个点，使得每个路径上都至少有一个点。
问题 2：给定一棵树，和 $m$ 条路径，求最多选出几个路径，使得任意两个路径不存在公共点。

下证明：这两个问题的答案相等。

类比区间时候的证明，设问题 1 答案为 $x$ ，问题 2 答案为 $y$ ，易证 $x\ge y$ 。

接下来证明能用 $y$ 个点覆盖完所有路径。用反证法，假设存在一个至少有 $y+1$ 个点的最佳答案，对于 $y$ 个不相交路径上面每个都至少有一个点，第 $y+1$ 个点如果在某个不相交路径内部，说明我们可以多选出一个不相交路径，在外部同理，矛盾，因此两个问题答案相同。

后面我们会分别从两个角度出发介绍两种算法，这两种算法都可以用来解决这两个题目。

算法 1（贪心，从树上用最少点覆盖路径角度出发）

求出答案

直接贪心。求出每个路径的顶点（也就是两个端点的 LCA），按照从深到浅的顺序一个一个取，如果已经被之前的点覆盖了就跳过。

证明：
根据归纳，我们只需要证明对于任意情况，选择最深的 LCA 不会让答案更劣就可以证明我们算法的正确性。

假设最深的路径为 $u\sim x\sim v$ ，其中 $x$ 是 $u,v$ 的 LCA。假设存在一个最优的答案没有取 $x$ ，因为这个路径上一定要取一个点，不失一般性，假设答案取了 $u\sim x$ （不含 $x$ ）上的某一个点 $p$ 。
只有当存在一条路径，使得该路径包含 $p$ 且不包含 $x$ ，我们的答案会更劣（否则取 $p$ 还是 $x$ 没有影响），这样的路径显然不存在，因为如果存在它的 LCA 一定更深。

如何维护一条路径是否被覆盖了？
这个问题抽象出来就是树上单点加，路径求和。当然可以用树链剖分 $O(n\log^2n)$ 解决，不过这个问题比较简单，是存在一种 $O(n\log n)$ 做法的。

维护 $d_u$ 表示 $u$ 到根的权值之和。
对于单点 $u$ 加上 $x$ 来说，其对 $d$ 的贡献是每个在 $u$ 子树内的 $d_v$ 都加上 $x$ 。
对于查询路径 $u,v$ ，答案就是 $d_u+d_v-d_{\operatorname{LCA}(u,v)}-d_{\textit{fa}_{\operatorname{LCA}(u,v)}}$ 。

那问题就转化成了子树加，单点求和。因为子树内 dfn 序连续，就是区间加，单点求和，用树状数组维护即可。

复杂度 $O(n\log n)$ ，参考代码见文末。

构造方案

构造应该选哪些点

贪心选出的点就是我们的答案。

构造应该选哪些路径

贪心选出的每个点都唯一对应一个路径，不难发现它们没有交点，那么这些路径就是我们的答案。

算法 2（dp，从树上选出最多不相交路径出发）

求出答案

把每条路径放在 LCA 处处理。
设 $dp_u$ 表示只考虑 $u$ 的子树，最多能取出多少条不相交的路径。

如果不选任何 LCA 为 $u$ 的路径， $dp_u \sum_{u\to v}dp_v$ ，也就是 $u$ 每个儿子的 $dp$ 之和。

如果选择了一条路径，要求出删去这个路径之后剩下的若干个子树的和。
设 $sum_u = \sum_{u\to v}dp_v$ 。

考虑在路径 $x\sim u \sim y$ 上的 $sum$ 之和，发现多计算了路径上这些点的 $dp$ 值，减去即可。

所以用两个树状数组维护单点修改，路径求和即可。

复杂度依然为 $O(n\log n)$ ，参考代码亦见文末。

构造方案

构造应该选哪些路径

dp 的同时维护 dp 的转移（不选任意一条路径，选了一个 LCA 在 u 的路径），然后遍历一遍树即可。

构造应该选哪些点

这个问题是困难的，我还没有想出来。

总结

这两种算法从不同的角度出发，能解决同一种问题。
但是贪心算法明显实现更简单，不过算法 2 的 dp 能用来解决路径带权的情况。（没有完爆）

参考代码与练习

练习

Gym101741C. Cover the Paths（树上用最少点覆盖路径，并输出方案）
参考代码（贪心）

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

const int N = 1e5+5;
int dp[N];

tuple<int,int,int> p[N];

int dep[N],dfn[N],sz[N],tot,fa[N][20];
vector<int> G[N];

void dfs1(int u,int f){
    dep[u] = dep[f] + 1;
    sz[u] = 1; dfn[u] = ++tot;
    fa[u][0] = f;
    for(int i=1;i<=__lg(dep[u]);i++){
        fa[u][i]=fa[fa[u][i-1]][i-1];
    }
    for(int v:G[u]){
        if(v==f)continue;
        dfs1(v,u);
        sz[u]+=sz[v];
    }
}
int lca(int u,int v){
    if(dep[u]>dep[v])swap(u,v);
    while(dep[u]<dep[v])v = fa[v][__lg(dep[v]-dep[u])];
    if(u==v)return u;
    for(int i=__lg(dep[u]);i>=0;i--){
        if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];
    }
    return fa[u][0];
}


int n,m;
struct BIT{
    int t[N];
    void add(int x,int v){
        if(!x)return; // 忽略 x = 0
        for(;x<=n;x+=x&-x)t[x]+=v;
    }
    int query(int x){
        int ans = 0;
        for(;x;x-=x&-x)ans+=t[x];
        return ans;
    }

    // type 1: 单点加，路径查询
    void add_u(int u,int x){
        add(dfn[u],x);
        add(dfn[u]+sz[u],-x);
    }
    int query_path(int u,int v){
        int w = lca(u,v);
        return query(dfn[u])+query(dfn[v])-query(dfn[w])-query(dfn[fa[w][0]]);
    }
}bit;



int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v;cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    dfs1(1,0);

    cin>>m;
    for(int i=1;i<=m;i++){
        int u,v;cin>>u>>v;
        int w = lca(u,v);
        p[i] = make_tuple(u,v,w);
    }

    sort(p+1,p+1+m, [](const tuple<int,int,int>& lhs,const tuple<int,int,int>& rhs){
        return dep[get<2>(lhs)]>dep[get<2>(rhs)];
    });

    int ans = 0;
    vector<int> res;
    for(int i=1;i<=m;i++){
        auto [u,v,w] = p[i];
        if(bit.query_path(u,v))continue;
        ++ans;
        res.push_back(w);
        bit.add_u(w,1);
    }

    cout << ans << '\n';
    for(int i=0;i<ans;i++)cout<<res[i]<<' ';
    cout<<'\n';
    return 0;
}

树上选出最多不相交路径，并输出方案
参考代码（dp）

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int dp[N];

int trans[N];
pair<int,int> p[N];
vector<int> l[N];

int dep[N],dfn[N],sz[N],tot,fa[N][20];
vector<int> G[N];



void dfs1(int u,int f){
    dep[u] = dep[f] + 1;
    sz[u] = 1; dfn[u] = ++tot;
    fa[u][0] = f;
    for(int i=1;i<=__lg(dep[u]);i++){
        fa[u][i]=fa[fa[u][i-1]][i-1];
    }
    for(int v:G[u]){
        if(v==f)continue;
        dfs1(v,u);
        sz[u]+=sz[v];
    }
}
int lca(int u,int v){
    if(dep[u]>dep[v])swap(u,v);
    while(dep[u]<dep[v])v = fa[v][__lg(dep[v]-dep[u])];
    if(u==v)return u;
    for(int i=__lg(dep[u]);i>=0;i--){
        if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];
    }
    return fa[u][0];
}


int n,m;
struct BIT{
    int t[N];
    void add(int x,int v){
        if(!x)return; // 忽略 x = 0
        for(;x<=n;x+=x&-x)t[x]+=v;
    }
    int query(int x){
        int ans = 0;
        for(;x;x-=x&-x)ans+=t[x];
        return ans;
    }

    // type 1: 单点加，路径查询
    void add_u(int u,int x){
        add(dfn[u],x);
        add(dfn[u]+sz[u],-x);
    }
    int query_path(int u,int v){
        int w = lca(u,v);
        return query(dfn[u])+query(dfn[v])-query(dfn[w])-query(dfn[fa[w][0]]);
    }

    // type 2: 路径加，单点查询
    void add_path(int u,int v,int x){
        add(dfn[u],x),add(dfn[v],x);
        int w = lca(u,v);
        add(dfn[w],-x),add(dfn[fa[w][0]],-x);
    }
    int query_u(int u){
        return query(dfn[u]+sz[u]-1)-query(dfn[u]-1);
    }
}valdp,valsum,check;

// 计算 dp 数组，以及记录转移
void dfs2(int u,int f){
    int sumdp = 0;
    
    for(int v:G[u]){
        if(v==f)continue;
        dfs2(v,u);
        dp[u] += dp[v];
    }

    sumdp = dp[u];
    valsum.add_u(u, sumdp);

    for(auto pid : l[u]){
        auto [x,y] = p[pid];
        auto res = valsum.query_path(x,y) - valdp.query_path(x,y) + 1;
        if(res > dp[u]){
            dp[u] = res;
            trans[u] = pid;
        }
    }

    valdp.add_u(u,dp[u]);
}

// 构造答案部分
vector<int> path_chosen;
int used_by[N];
void cover_path(int u,int v,int id){
    if(dep[u]>dep[v])swap(u,v);
    while(dep[u]!=dep[v]){
        used_by[v] = id;
        v = fa[v][0];
    }
    while(u!=v){
        used_by[u] = used_by[v] = id;
        u = fa[u][0], v = fa[v][0];
    }
    used_by[u] = id;    
}
void dfs3(int u,int f){
    if(!used_by[u] && trans[u]){
        cover_path(p[trans[u]].first,p[trans[u]].second,trans[u]);
        path_chosen.push_back(trans[u]);
    }

    for(int v:G[u]){
        if(v==f)continue;
        dfs3(v,u);
    }
}



int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v;cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    dfs1(1,0);

    cin>>m;
    for(int i=1;i<=m;i++){
        cin>>p[i].first>>p[i].second;
        l[lca(p[i].first,p[i].second)].push_back(i);
        check.add_path(p[i].first,p[i].second,1);
    }


    dfs2(1,0);

    cout << dp[1] << '\n';

    dfs3(1,0);

    for(auto pid:path_chosen){
        cout << pid <<' ';
    }
    cout<<'\n';
    return 0;
}

HDU5293 Tree chain problem（带权树上选出最大权不相交路径）
参考代码（dp）

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

using ll=long long;using ull=unsigned long long;

const int N = 1e5+5;
int dp[N];

tuple<int,int,int> p[N];
vector<int> l[N];

int dep[N],dfn[N],sz[N],tot,fa[N][20];
vector<int> G[N];

int n,m;
void dfs1(int u,int f){
    dep[u] = dep[f] + 1;
    sz[u] = 1; dfn[u] = ++tot;
    fa[u][0] = f;
    for(int i=1;i<20;i++){
        fa[u][i]=fa[fa[u][i-1]][i-1];
    }
    for(int v:G[u]){
        if(v==f)continue;
        dfs1(v,u);
        sz[u]+=sz[v];
    }
}
int lca(int u,int v){
    if(dep[u]>dep[v])swap(u,v);
    while(dep[u]<dep[v])v = fa[v][__lg(dep[v]-dep[u])];
    if(u==v)return u;
    for(int i=19;i>=0;i--){
        if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];
    }
    return fa[u][0];
}


struct BIT{
    ull t[N];
    void add(int x,ll v){
        if(!x)return; // 忽略 x = 0
        for(;x<=n;x+=x&-x)t[x]+=v;
    }
    ull query(int x){
        ull ans = 0;
        for(;x;x-=x&-x)ans+=t[x];
        return ans;
    }

    // type 1: 单点加，路径查询
    void add_u(int u,ll x){
        add(dfn[u],x);
        add(dfn[u]+sz[u],-x);
    }
    ll query_path(int u,int v){
        int w = lca(u,v);
        return query(dfn[u])+query(dfn[v])-query(dfn[w])-query(dfn[fa[w][0]]);
    }
}valdp,valsum;

// 计算 dp 数组，以及记录转移
void dfs2(int u,int f){
    ll sumdp = 0;
    
    for(int v:G[u]){
        if(v==f)continue;
        dfs2(v,u);
        dp[u] += dp[v];
    }

    sumdp = dp[u];
    valsum.add_u(u, sumdp);

    for(auto pid : l[u]){
        auto [x,y,w] = p[pid];
        auto res = valsum.query_path(x,y) - valdp.query_path(x,y) + w;
        if(res > dp[u]){
            dp[u] = res;
        }
    }

    valdp.add_u(u,dp[u]);
}



int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    
    int T;cin>>T;
    while(T--){
        cin>>n>>m;
        tot=0;
        memset(dp,0,sizeof(dp));
        memset(dep,0,sizeof(dep));
        memset(dfn,0,sizeof(dfn));
        memset(sz,0,sizeof(sz));
        memset(valdp.t,0,sizeof(valdp.t));
        memset(valsum.t,0,sizeof(valsum.t));

        for(int i=1;i<n;i++){
            int u,v;cin>>u>>v;
            G[u].push_back(v);
            G[v].push_back(u);
        }

        dfs1(1,0);

        for(int i=1;i<=m;i++){
            int x,y,z;cin>>x>>y>>z;
            p[i] = make_tuple(x,y,z);
            l[lca(x,y)].push_back(i);
        }


        dfs2(1,0);

        cout << dp[1] << '\n';

        
        for(int i=1;i<=n;i++){
            G[i].clear();
            l[i].clear();
        }
    }
    return 0;
}