【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 <bits/stdc++.h>
#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;
}