【Luogu】 P5642 人造情感（emotion）

题目链接

点击打开链接

题目解法

考虑如何计算 $f(U)$，我不知道如何能想到下面的解法

一个技巧是把路径挂在 $lca$ 上

我们令 $f_u$ 表示完全包含在 $u$ 的子树中的路径的最大独立集
考虑转移，记 $su{m}_u=\sum _{v\in son(u)}{f}_v$

1. 如果 $u$ 不在任何一条选中的路径上
   $f_u=su{m}_u$
2. $u$ 在权值为 $w$ 的路径 $x\to y$ 上
   考虑对于 $x\to u$ 和 $y\to u$ 的路径分别考虑，先给出式子：
   $f_u=su{m}_u+w-\sum _{q\in path(x,u)或q\in path(y,u)}(f_q-su{m}_q)$
   需要减去 $f_q-su{m}_q$ 是因为 $path(x,y)$ 上的点都不能被选在其他的路径上，而我们的状态天然契合 $f_q-su{m}_q$ 是 $q$ 不在 $q$ 子树路径上的方案数

上面的东西可以用 $BIT$ 维护，具体来说，它需要实现单点加，链查，而因为遍历树的独特结构，所以我们可以把它变成子树加，单点查

同时我们需要另一个数组 $g_u$ 表示 $u$ 子树外的路径的最大独立集
继续考虑分类转移，我们这里考虑用 $g_u$ 的答案推导 $g_v(v\in son(u))$ 的答案

1. $u$ 不在任何一条路径上
   $g_v=g_u+su{m}_u-f_v$
2. $u$ 在权值为 $w$ 的路径 $x\to y$ 上，$x\to y$ 不经过 $v$
   令 $x,y$ 的 $lca$ 为 $h$
   不难得出这个式子：
   $g_v=g_h+w+su{m}_h-\sum _{q\in path(x,y)}(f_q-su{m}_q)-f_v$

上面的东西可以把树拍平成 $dfs$ 序，然后线段树做，注意要特殊考虑 $lca=u$ 的情况

最后就可以考虑计算答案
暴力计算我在程序中用注释标出了，然后就是优化这个暴力，这个不算太难，注意一些细节即可

时间复杂度 $O(nlogn)$

#include 
#define int long long
#define lowbit(x) x&-x
#define pb push_back
using namespace std;
const int N=300100,P=998244353;
struct Lines{ int u,v,w;};
int n,m,ans;
int depth[N],up[N][20],siz[N];
int Ldfn[N],Rdfn[N],dfs_clock;
int f[N],sum[N];//f[u]：u子树内不交路径的权值之和
int g[N];//g[u]:u子树外不交路径的权值之和
int e[N<<1],ne[N<<1],h[N],idx;
vector<int> G[N];
vector<Lines> ln[N];
inline int read(){
    int FF=0,RR=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    return FF*RR;
}
void predfs(int u,int fa){
    depth[u]=depth[fa]+1;
    Ldfn[u]=++dfs_clock,up[u][0]=fa;
    for(int i=h[u];~i;i=ne[i]) if(e[i]!=fa) G[u].pb(e[i]),predfs(e[i],u);
    Rdfn[u]=dfs_clock;
}
int get_lca(int x,int y){
    if(depth[x]>depth[y]) swap(x,y);
    for(int i=18;i>=0;i--) if(depth[up[y][i]]>=depth[x]) y=up[y][i];
    if(x==y) return x;
    for(int i=18;i>=0;i--) if(up[x][i]!=up[y][i]) x=up[x][i],y=up[y][i];
    return up[x][0];
}
struct BIT{
    int tr[N];
    void inc(int x,int v){ for(;x<=n;x+=lowbit(x)) tr[x]+=v;}
    void add(int l,int r,int v){ inc(l,v),inc(r+1,-v);}
    int ask(int x){
        int res=0;
        for(;x;x-=lowbit(x)) res+=tr[x];
        return res;
    }
}BIT;
struct SGT{
    int seg[N<<2];
    void modify(int l,int r,int x,int pos,int v){
        if(l==r){ seg[x]=max(seg[x],v);return;}
        int mid=(l+r)>>1;
        if(mid>=pos) modify(l,mid,x<<1,pos,v);
        else modify(mid+1,r,x<<1^1,pos,v);
        seg[x]=max(seg[x<<1],seg[x<<1^1]);
    }
    int query(int l,int r,int x,int L,int R){
        if(L<=l&&r<=R) return seg[x];
        int mid=(l+r)>>1;
        if(mid>=L&&mid<R) return max(query(l,mid,x<<1,L,R),query(mid+1,r,x<<1^1,L,R));
        if(mid>=L) return query(l,mid,x<<1,L,R);
        return query(mid+1,r,x<<1^1,L,R);
    }
    void upd(int pos,int v){ modify(1,n,1,pos,v);}
    int ask(int l1,int r1,int l2,int r2){
        int ret=0;
        if(l1<l2) ret=max(ret,query(1,n,1,l1,l2-1));
        if(r2<r1) ret=max(ret,query(1,n,1,r2+1,r1));
        return ret;
    }
}sg;
void calc_f(int u){
    for(int v:G[u]) calc_f(v),sum[u]+=f[v];
    //u不在路径上
    f[u]=sum[u];
    //u在路径上
    for(auto &E:ln[u]){
        E.w+=sum[u]-BIT.ask(Ldfn[E.u])-BIT.ask(Ldfn[E.v]);
        f[u]=max(f[u],E.w);
        //单点加+链求和+dfs的性质->子树加，单点查，单log
    }
    BIT.add(Ldfn[u],Rdfn[u],f[u]-sum[u]);
}
void calc_g(int u){
    sort(ln[u].begin(),ln[u].end(),[&](Lines x,Lines y){ return x.w>y.w;});
    for(int v:G[u]){
        g[v]=g[u]+sum[u]-f[v];
        for(auto E:ln[u])
            if(get_lca(E.u,v)!=v&&get_lca(E.v,v)!=v){//u,v没有一端在v的子树中
                g[v]=max(g[v],E.w+g[u]-f[v]);break;
            }
        g[v]=max(g[v],sg.ask(Ldfn[u],Rdfn[u],Ldfn[v],Rdfn[v])-f[v]);
    }
    for(auto E:ln[u]) sg.upd(Ldfn[E.u],E.w+g[u]),sg.upd(Ldfn[E.v],E.w+g[u]);
    for(int v:G[u]) calc_g(v);
}
void calc_ans(int u){
    int res=0;
    for(int v:G[u]) calc_ans(v),res=(res+siz[u]*siz[v])%P,siz[u]+=siz[v];
    siz[u]++;
    ans-=(g[u]+f[u])%P*(2*res+2*siz[u]-1)%P;
    res=(2*(siz[u]-1)*(n-siz[u])%P+2*res+2*n-1)%P;
    ans+=(f[u]-sum[u])%P*res%P;
    ans=(ans%P+P)%P;
}
void add(int x,int y){ e[idx]=y,ne[idx]=h[x],h[x]=idx++;}
// int get_sum(int x,int y){
//     int lca=get_lca(x,y),res=0;
//     while(x!=lca) res+=f[x]-sum[x],x=up[x][0];
//     while(y!=lca) res+=f[y]-sum[y],y=up[y][0];
//     res+=f[lca]-sum[lca];
//     return res;
// }
signed main(){
    n=read(),m=read();
    memset(h,-1,sizeof(h));
    for(int i=1;i<n;i++){
        int x=read(),y=read();
        add(x,y),add(y,x);
    }
    predfs(1,-1);
    for(int j=1;j<=18;j++) for(int i=1;i<=n;i++) up[i][j]=up[up[i][j-1]][j-1];
    for(int i=1;i<=m;i++){
        int u=read(),v=read(),w=read();
        int lca=get_lca(u,v);
        ln[lca].pb({u,v,w});
    }
    calc_f(1),calc_g(1),calc_ans(1);
    ans=(ans+f[1]%P*n%P*n)%P;
    // for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
    //     ans+=f[1]-g[get_lca(i,j)]-f[get_lca(i,j)]+get_sum(i,j);
    printf("%lld\n",ans);
    fprintf(stderr,"%d ms\n",int64_t(1e3*clock()/CLOCKS_PER_SEC));
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134