题解 P4315 【月下“毛景树”】
VenusM1nT
2019-01-07 10:58:59
树链剖分。俗话说得好，$\text{OI}$ 毒瘤千千万，树剖 $\text{DP}$ 各一半。（纯属瞎扯，很多数据结构也很毒瘤），这道题很明显的是一道树链剖分的题，但因为操作的对象是**边权**，而树链剖分针对的应该是**点权**，所以我们要将边权转为点权来做。
此时很明显，我们会想到**将一条边的边权转移到它深度更深的端点**上，然后进行处理，但此时会有一个问题，也就是在查询路径 $u-v$ 时，$u$ 和 $v$ 的 $lca$ 的权值是它上一条边的权值，并不属于 $u-v$ 这条路径，所以我们在退出 $top[u]\not= top[v]$ 这层循环，进行最后一次操作时应将 $u$ 的 $\text{DFS}$ 序加上 $1$ ，这样就可以忽略 $lca$ 这个点了。
具体原因表述可能不太清楚：在退出循环之后，两个点的位置在同一条重链上，显然，这条重链的 $top$ 就是它们原来的 $lca$，而要忽略 $lca$ ，就是要到达比它深度 $+1$ 的点，这个点的 $\text{DFS}$ 序也显然是比 $lca$ 的 $\text{DFS}$ 序多 $1$。
最后讲一下线段树的注意事项，这题有一个比较少见的操作：区间覆盖，我们多设置一个 $\text{lazytag}$，命名为 $cov$，记录区间覆盖情况，然后在 $\text{pushdown}$ 时先处理这个 $cov$，处理完后不能重新赋值为 $0$ ，而是要赋值为 $-1$，为什么呢？因为区间覆盖的值可能为 $0$，但不可能为负数（毕竟不可能有 $-1$ 个毛毛果），初值也要赋成 $-1$。
```cpp
#include<bits/stdc++.h>
#define MAXN 100005
using namespace std;
int cnt,fst[MAXN],nxt[MAXN<<1],to[MAXN<<1],w[MAXN<<1],fr[MAXN<<1];
int n,a[MAXN],t[MAXN<<2],tag[MAXN<<2],cov[MAXN<<2];
int siz[MAXN],son[MAXN],dfn[MAXN],Index,top[MAXN],rk[MAXN],dep[MAXN],faz[MAXN];
string s;
void AddEdge(int u,int v,int c)
{
to[++cnt]=v;
nxt[cnt]=fst[u];
fst[u]=cnt;
w[cnt]=c;
fr[cnt]=u;
}
void Dfs1(int u)
{
siz[u]=1;
son[u]=0;
for(int i=fst[u];i;i=nxt[i])
{
int v=to[i];
if(v==faz[u]) continue;
faz[v]=u;
dep[v]=dep[u]+1;
rk[v]=w[i];
Dfs1(v);
siz[u]+=siz[v];
if(siz[son[u]]<siz[v]) son[u]=v;
}
}
void Dfs2(int u,int rt)
{
dfn[u]=++Index;
top[u]=rt;
a[Index]=rk[u];
if(son[u]) Dfs2(son[u],rt);
for(int i=fst[u];i;i=nxt[i])
{
int v=to[i];
if(v==faz[u] || v==son[u]) continue;
Dfs2(v,v);
}
}
void PushUp(int rt)
{
t[rt]=max(t[rt<<1],t[rt<<1|1]);
}
void PushDown(int rt)
{
if(~cov[rt])
{
cov[rt<<1]=cov[rt<<1|1]=cov[rt];
t[rt<<1]=t[rt<<1|1]=cov[rt];
tag[rt<<1]=tag[rt<<1|1]=0;
cov[rt]=-1;
}
tag[rt<<1]+=tag[rt];
tag[rt<<1|1]+=tag[rt];
t[rt<<1]+=tag[rt];
t[rt<<1|1]+=tag[rt];
tag[rt]=0;
}
void BuildSegmentTree(int rt,int l,int r)
{
cov[rt]=-1;
if(l==r)
{
t[rt]=a[l];
return;
}
int mid=l+r>>1;
BuildSegmentTree(rt<<1,l,mid);
BuildSegmentTree(rt<<1|1,mid+1,r);
PushUp(rt);
}
void ModifyCover(int rt,int l,int r,int tl,int tr,int val)
{
if(tl<=l && r<=tr)
{
t[rt]=cov[rt]=val;
tag[rt]=0;
return;
}
PushDown(rt);
int mid=l+r>>1;
if(tl<=mid) ModifyCover(rt<<1,l,mid,tl,tr,val);
if(tr>mid) ModifyCover(rt<<1|1,mid+1,r,tl,tr,val);
PushUp(rt);
}
void ModifyAdd(int rt,int l,int r,int tl,int tr,int val)
{
if(tl<=l && r<=tr)
{
t[rt]+=val;
tag[rt]+=val;
return;
}
PushDown(rt);
int mid=l+r>>1;
if(tl<=mid) ModifyAdd(rt<<1,l,mid,tl,tr,val);
if(tr>mid) ModifyAdd(rt<<1|1,mid+1,r,tl,tr,val);
PushUp(rt);
}
int Query(int rt,int l,int r,int tl,int tr)
{
if(tl<=l && r<=tr) return t[rt];
PushDown(rt);
int mid=l+r>>1,res=0;
if(tl<=mid) res=max(res,Query(rt<<1,l,mid,tl,tr));
if(tr>mid) res=max(res,Query(rt<<1|1,mid+1,r,tl,tr));
return res;
}
void ModifyCoverOnTree(int u,int v,int val)
{
while(top[u]!=top[v])
{
if(dep[top[u]]<dep[top[v]]) swap(u,v);
ModifyCover(1,1,n,dfn[top[u]],dfn[u],val);
u=faz[top[u]];
}
if(dep[u]>dep[v]) swap(u,v);
ModifyCover(1,1,n,dfn[u]+1,dfn[v],val);
}
void ModifyAddOnTree(int u,int v,int val)
{
while(top[u]!=top[v])
{
if(dep[top[u]]<dep[top[v]]) swap(u,v);
ModifyAdd(1,1,n,dfn[top[u]],dfn[u],val);
u=faz[top[u]];
}
if(dep[u]>dep[v]) swap(u,v);
ModifyAdd(1,1,n,dfn[u]+1,dfn[v],val);
}
int QueryMaxnOnTree(int u,int v)
{
int res=0;
while(top[u]!=top[v])
{
if(dep[top[u]]<dep[top[v]]) swap(u,v);
res=max(res,Query(1,1,n,dfn[top[u]],dfn[u]));
u=faz[top[u]];
}
if(dep[u]>dep[v]) swap(u,v);
res=max(res,Query(1,1,n,dfn[u]+1,dfn[v]));
return res;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int x,y,z;
scanf("%d %d %d",&x,&y,&z);
AddEdge(x,y,z);
AddEdge(y,x,z);
}
Dfs1(1);
Dfs2(1,1);
BuildSegmentTree(1,1,n);
while(1)
{
int x,y,z;
cin>>s;
if(s=="Stop") break;
else
{
scanf("%d %d",&x,&y);
if(s=="Change")
{
x<<=1;
int u=fr[x],v=to[x];
if(dep[u]>dep[v]) swap(u,v);
ModifyCoverOnTree(u,v,y);
}
else if(s=="Cover")
{
scanf("%d",&z);
ModifyCoverOnTree(x,y,z);
}
else if(s=="Add")
{
scanf("%d",&z);
ModifyAddOnTree(x,y,z);
}
else if(s=="Max") printf("%d\n",QueryMaxnOnTree(x,y));
}
}
return 0;
}
```