P7563 JOISC 2021 Day4 最悪の記者 4 (Worst Reporter 4)
线段树合并好题，通过线段树合并特别的方式优化了树形 dp。
思路
根据图中的不等关系连边建图，不难发现最后的图将会是基环树森林和普通的树的森林，我们先考虑对于一棵树要怎么办。
将 \(h_i\) 离散化，\(m\) 为离散化上界，使用树形 dp。
设 \(f_{i,j}\) 为将 \(i\) 改成 \(j\) 使 \(i\) 的子树内满足不等关系的最小花费。
\[f_{i,j}=c_i\times[j\neq h_i]+\sum_{k\in i.sons} \min_{j\leq t \leq m} f_{k,t} \]这个 dp 是超时的，但是是正确的，我们考虑优化 dp 转移。
我们发现每个都加上 \(c_i\) 对我们操作有点麻烦，我们在最后求出答案是同一加上 \(\sum c_i\)，将方程改为
\[f_{i,j}=\sum_{k\in i.sons}\min_{j\leq t\leq m} f_{k,t} -c_i*[j=h_i] \]为什么这样操作呢？
由于转移只有区间最小值查询和减法操作，考虑线段树维护 \(f\) 值。
线段树的区间维护一个节点的状态的第二维，点取值维护对应区间的最小值，区间 \([l,r]\) 维护的是 \(\min_{l\leq i\leq r} f_{u,i}\)。
每个点开一棵肯定不现实，考虑线段树合并，每一次合并就相当于父亲和儿子做一次转移。
找区间最小值的区间是 \([j,m]\)，合并树 \(u\) 和树 \(v\) 时，计 \(u_{min}\) 和 \(v_{min}\) 为各自的最小值（在区间 \([j,m]\) 内），对于节点 \(p\) 和 \(q\) 分类讨论 \(p+v_{min}\) 和 \(q+u_{min}\) 哪个最小（这里实际上和转移有关，可以钦定父子关系，从转移方程的角度分析），将较小值设置即可。
由于最小值右端点固定，启发性的先合并右子树，便于维护最小值。
对于每个点的初始更新，在 \([h_i,h_i]\) 出加上 \(-c_i\) 即可。
扩展到基环树，发现基环树的环上的点肯定是同一取值，且要么是 \(1\) 要么是环上取值。
那么先求出基环树的环上节点的 \(f\) 状态，最后枚举环上的点的取值即可。
CODE
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lch(p) tree[p].lch
#define rch(p) tree[p].rch
const int maxn=2e5+5;
int rb;
struct linetree
{
int tot;
ll d1,d2;
struct treenode{int lch,rch;ll lazy,mi;}tree[maxn*57];
void push_down(int p)//下传懒标记
{
if(!tree[p].lazy) return ;
ll &lazy=tree[p].lazy;
if(lch(p)) tree[lch(p)].lazy+=lazy,tree[lch(p)].mi+=lazy;
if(rch(p)) tree[rch(p)].lazy+=lazy,tree[rch(p)].mi+=lazy;
lazy=0;
}
void updata(int p)
{
tree[p].mi=min(tree[lch(p)].mi,tree[rch(p)].mi);
}
void insert(int &p,int l,int r,int x,ll y)
{
if(l>x||r<x) return ;
if(!p) p=++tot;
if(l==r){tree[p].mi=y;return ;}
push_down(p);
int mid=(l+r)>>1;
insert(lch(p),l,mid,x,y);
insert(rch(p),mid+1,r,x,y);
updata(p);
}
ll qry(int p,int l,int r,int lx,int rx)//查询区间最小值
{
if(!p) return 0;
if(lx<=l&&r<=rx) return tree[p].mi;
if(lx>r||rx<l) return 0;
push_down(p);
int mid=(l+r)>>1;
return min(qry(lch(p),l,mid,lx,rx),qry(rch(p),mid+1,r,lx,rx));
}
void merge(int &p1,int p2,int l,int r)//合并
{
if(!p1&&!p2) return ;
if(!p1)
{
d2=min(d2,tree[p2].mi);
tree[p2].mi+=d1;
tree[p2].lazy+=d1;
p1=p2;
return ;
}
else if(!p2)
{
d1=min(d1,tree[p1].mi);
tree[p1].mi+=d2;
tree[p1].lazy+=d2;
return ;
}
if(l==r)
{
d1=min(d1,tree[p1].mi),d2=min(d2,tree[p2].mi);
if(tree[p1].mi+d2<=tree[p2].mi+d1){tree[p1].mi=tree[p1].mi+d2;}
else{tree[p1].mi=tree[p2].mi+d1;}
return ;
}
push_down(p1);
push_down(p2);
int mid=(l+r)>>1;
merge(rch(p1),rch(p2),mid+1,r);//启发式
merge(lch(p1),lch(p2),l,mid);
updata(p1);
}
void premrg(int &x,int y)
{
d1=d2=0;
merge(x,y,1,rb);
}
}T;
struct Edge
{
int tot;
int head[maxn];
struct edgenode{int to,nxt;}edge[maxn*2];
void add(int u,int v)
{
tot++;
edge[tot].to=v;
edge[tot].nxt=head[u];
head[u]=tot;
}
}E;
int n,tot;
int a[maxn],h[maxn],c[maxn],ind[maxn],d[maxn],dfn[maxn];
int rt[maxn],nt[maxn];
struct node{ll h,c;};
bool cmp(node a,node b){return a.h<b.h;}
vector<node>cr[maxn];
ll ans;
void pushcir(int u)//同一个环赋予同一编号
{
dfn[u]=tot;
cr[tot].push_back({h[u],c[u]});
if(!dfn[a[u]]) pushcir(a[u]);
}
void gtp()//找环
{
queue<int>que;
while(!que.empty()) que.pop();
for(int i=1;i<=n;i++) if(!ind[i]) que.push(i);
while(!que.empty())
{
int u=que.front();que.pop();
if(!--ind[a[u]]) que.push(a[u]);
}
for(int i=1;i<=n;i++)//可能有多个环，tot 是环数
if(!dfn[i]&&ind[i]) tot++,pushcir(i);
}
void dfs(int u)//求 u 的状态
{
for(int i=E.head[u];i;i=E.edge[i].nxt)
{
int v=E.edge[i].to;
dfs(v);
T.premrg(rt[u],rt[v]);//合并儿子和自己
}
T.insert(rt[u],1,rb,h[u],T.qry(rt[u],1,rb,h[u],rb)-c[u]);
//insert 更改区间 [h[u],h[u]] 的值
}
void calc()
{
for(int i=1;i<=n;i++) if(!ind[i]&&ind[a[i]])//求环的状态
dfs(i),T.premrg(nt[dfn[a[i]]],rt[i]);
for(int i=1;i<=tot;i++)
{
sort(cr[i].begin(),cr[i].end(),cmp);
ll cnt=T.tree[nt[i]].mi,sh=cr[i][0].h,sc=0;
for(node v:cr[i])
{
if(v.h==sh) sc+=v.c;
else
{
cnt=min(cnt,T.qry(nt[i],1,rb,sh,rb)-sc);
sh=v.h,sc=v.c;
}
}
cnt=min(cnt,T.qry(nt[i],1,rb,sh,rb)-sc);
ans+=cnt;
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&a[i],&h[i],&c[i]);
E.add(a[i],i);
ind[a[i]]++;
d[i]=h[i];
ans+=c[i];
}
sort(d+1,d+n+1);
rb=unique(d+1,d+n+1)-d-1;
for(int i=1;i<=n;i++) h[i]=lower_bound(d+1,d+rb+1,h[i])-d;//离散化
gtp();
calc();
printf("%lld",ans);
}