题解：P15831 [JOI Open 2015] 选举活动 / Election Campaign

· · 题解

一道并不困难的树链剖分。

思路

我们设 f_u 为选完 u 子树内能获得的最大收益。考虑如何转移。

一种是不选，就是 \sum\limits_{v\in \text{son}\left(u\right)} f_v。
还有一种就是选两端点 LCA 为 u 的一个路径。假设这条路径的权值为 w。我们设路径点集为 V，那么答案是：

\left(\sum\limits_{\text{fa}_x\in V\wedge x\notin V} f_x\right)+w

这样直接转移是 \mathcal{O}\left(n^2\right) 的。尝试优化这个 DP。
我们设 g_u=\sum\limits_{v\in \text{son}\left(u\right)} f_v。第一个显然是 g_u，第二个是 \left(\sum\limits_{x\in V}\left(g_x-f_x\right)\right)+w。这里 f_u=0。

直接树链剖分做完了。

:::success[代码]

#include <bits/stdc++.h>
using namespace std;
#define debug cerr<<"The code runs successfully.\n";
#define endl '\n'
#define TRACE 1
#define tcout TRACE && cout
#define fst ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define int long long
#define fir first
#define sec second
const int P = 998244353;
const int Base = 33331;
#ifdef int
const int INF = 0x3f3f3f3f3f3f3f3f;
#else
const int INF = 0x3f3f3f3f;
#endif
const int N = 1e5 + 10, M = 1e6 + 10;
int n,dp[N],sum[N],siz[N],m,dfn[N],son[N],top[N],idx,dep[N],fa[N];
vector<int> g[N];
vector<pair<pair<int,int>,int>> chain[N];
struct FenwickTree {//树状数组
    int tr[N];
    inline void add(int x,int k) {
        for(;x<=n;x+=x&-x) tr[x]+=k;
    }
    inline int ask(int x) {
        int res=0;
        for(;x;x-=x&-x) res+=tr[x];
        return res;
    }
    inline int ask(int l,int r) {
        return ask(r)-ask(l-1);
    }
} tr1,tr2;//tr1维护f tr2维护g
void dfs1(int u,int f) {
    siz[u]=1,fa[u]=f,dep[u]=dep[f]+1;
    for(int v:g[u]) {
        if(v==f) continue;
        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[son[u]]<siz[v]) son[u]=v;
    }
}
void dfs2(int u,int f) {
    dfn[u]=++idx,top[u]=f;
    if(son[u]) dfs2(son[u],f);
    for(int v:g[u]) {
        if(v==fa[u]||v==son[u]) continue;
        dfs2(v,v);
    }
}
inline int lca(int u,int v) {//树剖LCA
    while(top[u]!=top[v]) {
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        u=fa[top[u]];
    }
    if(dep[u]>dep[v]) swap(u,v);
    return u;
}
inline void add(int u,int k) {
    tr1.add(dfn[u],k);
    if(fa[u]) tr2.add(dfn[fa[u]],k);
}
inline int ask1(int u,int v) {//查询链上和
    int res=0;
    while(top[u]!=top[v]) {
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        res+=tr1.ask(dfn[top[u]],dfn[u]);
        u=fa[top[u]];
    }
    if(dep[u]>dep[v]) swap(u,v);
    res+=tr1.ask(dfn[u],dfn[v]);
    return res;
}
inline int ask2(int u,int v) {
    int res=0;
    while(top[u]!=top[v]) {
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        res+=tr2.ask(dfn[top[u]],dfn[u]);
        u=fa[top[u]];
    }
    if(dep[u]>dep[v]) swap(u,v);
    res+=tr2.ask(dfn[u],dfn[v]);
    return res;
}
void solve(int u) {
    for(int v:g[u]) {
        if(v!=fa[u]) solve(v);
    }
    int res=ask2(u,u);//不选
    for(auto e:chain[u]) {
        res=max(res,ask2(e.fir.fir,e.fir.sec)-ask1(e.fir.fir,e.fir.sec)+e.sec);//选
    }
    add(u,res);
}
signed main() {
    // freopen("paths.in","r",stdin);
    // freopen("paths.out","w",stdout);
    fst;
    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);
    dfs2(1,1);
    cin>>m;
    for(int i=1;i<=m;i++) {
        int u,v,w;
        cin>>u>>v>>w;
        chain[lca(u,v)].push_back({{u,v},w});
    }
    solve(1);
    cout<<ask1(1,1)<<endl;
    return 0;
}

:::