题解 P4315 【月下“毛景树”】
Juan_feng
2018-08-29 18:39:16
### 总算是A掉这道题了qwq
真是把小蒟蒻我给榨干了qwq
A掉这道题经过了两天多的努力和一些神奇的经历（有兴趣可以自行观看讨论
**咳咳，进入正题**
**这道题其实就是一个裸的边权树剖，不会树剖的可以右转P3384树剖模板**
小蒟蒻一开始很快想到思路就来做这道题，但做完了就发现到处都是问题（果然还是我太菜了qwq），其实这道题的细节部分好像也不是很复杂，稍微注意一下就好了qwq
#### 有几点需要注意：
1：树剖维护的是边权，可以**把边权转化到点权上**。
怎么转化呢？因为每个孩子节点通向父节点的边是唯一的，所以可以将每个边的边权转到边所连的孩子节点上（可在树剖的第一个dfs中完成）
2：修改一条链上的权值时，要注意链两端的点的**lca不能够被修改**，因为lca所对应的边权不在这一条链上。
3：Change 操作是修改**第k条**树枝，**k为读入的顺序**，而树的存边是双向的，所以要将读入的k乘以二在进行后面的操作。
4：下推标记的时候如果有覆盖标记不要忘了**清除加的标记**。
上面几点有的之前的dalao已经说过了，权当是再做一次总结
注意了以上几点，程序自然就不在话下了qwq
感谢@rehtorbegnaro以及其他dalao的帮助和支持
**献上233行代码**233
```
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define maxn 2000010
#define ll long long
#define re register
#define FOR(i,l,r) for(re ll i=l;i<=r;i++)
using namespace std;
ll tag1[maxn<<2],tag2[maxn<<2],ans[maxn<<2],head[maxn<<1],a[maxn];//tag1为覆盖，tag2为加
ll top[maxn],son[maxn],depth[maxn],fa[maxn],siz[maxn],id[maxn],dd[maxn];
ll n,m,k,t,num,cnt,x,y,z,w,q;
string s;
struct hz{
ll next;
ll to;
ll dis;
ll from;
}h[maxn<<1];
inline void in(ll &x){ //快读使我快乐
x=0;ll f=1;char c=getchar();
while(c<'0'||c>'9'){
if(c==-1) return;
if(c=='-')f=-1;
c=getchar();
}
while(c<='9'&&c>='0'){
x=(x<<1)+(x<<3)+(c^'0');
c=getchar();
}
x=x*f;
}
inline void out(ll a){
if(a<0){
a*=-1;
putchar('-');
}
if(a>=10)out(a/10);
putchar(a%10+'0');
}
inline void add(ll from,ll to,ll dis){ //邻接表存边
h[++num].next=head[from];
h[num].to=to;
h[num].from=from;
h[num].dis=dis;
head[from]=num;
}
//------------------------------以下为线段树部分
inline ll ls(ll k){
return k<<1;
}
inline ll rs(ll k){
return k<<1|1;
}
inline void push_up(ll k){
ans[k]=max(ans[ls(k)],ans[rs(k)]);
}
inline void push_down(ll p){ //下推标记
if(tag1[p]!=-1){ //下推覆盖标记时要清楚加标记
tag1[ls(p)]=tag1[rs(p)]=tag1[p];
ans[ls(p)]=ans[rs(p)]=tag1[p];
tag2[ls(p)]=tag2[rs(p)]=0;
tag1[p]=-1;
}
tag2[ls(p)]+=tag2[p];
tag2[rs(p)]+=tag2[p];
ans[ls(p)]+=tag2[p];
ans[rs(p)]+=tag2[p];
tag2[p]=0;
}
void update1(ll nl,ll nr,ll l,ll r,ll p,ll k){ //区间覆盖
if(nl<=l&&r<=nr){
ans[p]=k;
tag1[p]=k;
tag2[p]=0;
return;
}
ll mid=(l+r)>>1;
push_down(p);
if(nl<=mid) update1(nl,nr,l,mid,ls(p),k);
if(nr>mid) update1(nl,nr,mid+1,r,rs(p),k);
push_up(p);
}
void update2(ll nl,ll nr,ll l,ll r,ll p,ll k){ //区间加
if(nl<=l&&r<=nr){
ans[p]+=k;
tag2[p]+=k;
return;
}
ll mid=(l+r)>>1;
push_down(p);
if(nl<=mid) update2(nl,nr,l,mid,ls(p),k);
if(nr>mid) update2(nl,nr,mid+1,r,rs(p),k);
push_up(p);
}
ll query(ll q_x,ll q_y,ll l,ll r,ll p){ //区间求Max
if(q_x<=l&&r<=q_y)
return ans[p];
ll res=0;
ll mid=(l+r)>>1;
push_down(p);
if(q_x<=mid) res=max(res,query(q_x,q_y,l,mid,ls(p)));
if(q_y>mid) res=max(res,query(q_x,q_y,mid+1,r,rs(p)));
return res;
}
void build(ll p,ll l,ll r){ //建树
tag1[p]=-1;
tag2[p]=0;
if(l==r){
ans[p]=dd[l];
return;
}
ll mid=(l+r)>>1;
build(ls(p),l,mid);
build(rs(p),mid+1,r);
push_up(p);
}
//------------------------------以上为线段树部分
void dfs1(ll f,ll ff){
depth[f]=depth[ff]+1;
fa[f]=ff;
siz[f]=1;
ll maxson=-1;
for(re ll i=head[f];i!=0;i=h[i].next){
if(h[i].to==ff)
continue;
dfs1(h[i].to,f);
a[h[i].to]=h[i].dis; //把边权化为点权
siz[f]+=siz[h[i].to];
if(siz[h[i].to]>maxson){
maxson=siz[h[i].to];
son[f]=h[i].to;
}
}
}
void dfs2(ll x,ll topf){
top[x]=topf;
id[x]=++cnt;
dd[cnt]=a[x];
if(!son[x])
return;
dfs2(son[x],topf);
for(re ll i=head[x];i!=0;i=h[i].next){
if(h[i].to==fa[x]||h[i].to==son[x])
continue;
dfs2(h[i].to,h[i].to);
}
}
void updrange1(ll x,ll y,ll k){ //Change和Cover操作
while(top[x]!=top[y]){
if(depth[top[x]]<depth[top[y]])
swap(x,y);
update1(id[top[x]],id[x],1,n,1,k);
x=fa[top[x]];
}
if(depth[x]>depth[y])
swap(x,y);
update1(id[x]+1,id[y],1,n,1,k); //不能更新lca所以是(id[x]+1)
}
void updrange2(ll x,ll y,ll k){ //Add操作
while(top[x]!=top[y]){
if(depth[top[x]]<depth[top[y]])
swap(x,y);
update2(id[top[x]],id[x],1,n,1,k);
x=fa[top[x]];
}
if(depth[x]>depth[y])
swap(x,y);
update2(id[x]+1,id[y],1,n,1,k); //同上
}
ll qrange(ll x,ll y){ //Max操作
ll anss=0;
while(top[x]!=top[y]){
if(depth[top[x]]<depth[top[y]])
swap(x,y);
anss=max(anss,query(id[top[x]],id[x],1,n,1));
x=fa[top[x]];
}
if(depth[x]>depth[y])
swap(x,y);
return max(anss,query(id[x]+1,id[y],1,n,1));//同理
}
int main(){
in(n);
FOR(i,1,n-1){
in(x),in(y),in(z);
add(x,y,z);
add(y,x,z); //双向加边
}
dfs1(1,0);
dfs2(1,1);
build(1,1,n);
while(s!="Stop"){
if(s[1]=='h'){
in(x),in(k);
x*=2; //因为边有重复的，所以乘以二保证是第K条边
x=depth[h[x].from]>depth[h[x].to]?h[x].from:h[x].to;//深度大的点（子节点）保存权值
update1(id[x],id[x],1,n,1,k); //Change操作
}
if(s[1]=='o'){
in(x),in(y),in(z);
updrange1(x,y,z); //Cover操作
}
if(s[1]=='d'){
in(x),in(y),in(z);
updrange2(x,y,z); //Add操作
}
if(s[1]=='a'){
in(x),in(y);
out(qrange(x,y)); //Max操作
puts("");
}
cin>>s;
}
return 0; //功德圆满
}
```