P4315 【月下“毛景树”】
Captain_Paul
2018-03-28 21:55:49
一道~~毒瘤~~树链剖分
主要思想就是把边权化为点权
与P1505 旅游有些类似
先进行dfs,之后枚举编号为奇数的边
使奇数边的to比from的深度大
然后把边权存为to的点权即可
维护一个区间加法标记和一个区间覆盖标记
接下来就是普通线段树操作了
~~我才不会说我少打一个pushdown调了两个小时~~
感谢@da32s1da 大佬的帮助!
丑陋的代码:
```cpp
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define reg register
using namespace std;
const int N=1e5+5;
struct edge
{
int from,to,nxt,dis;
}edge[N<<1];
int n,num,head[N],fa[N],son[N],tot[N],tag[N<<2];
int cnt,idx[N],top[N],dep[N],w[N],maxn[N<<2],lazy[N<<2];
inline int read()
{
int x=0,w=1;
char c=getchar();
while (!isdigit(c)&&c!='-') c=getchar();
if (c=='-') c=getchar(),w=-1;
while (isdigit(c))
{
x=(x<<1)+(x<<3)+c-'0';
c=getchar();
}
return x*w;
}
inline void add_edge(int from,int to,int dis)
{
edge[++num].nxt=head[from];
edge[num].from=from;
edge[num].to=to;
edge[num].dis=dis;
head[from]=num;
}
void dfs(int k,int father,int deep)
{
int bigson=0;
fa[k]=father; dep[k]=deep; tot[k]=1;
for (reg int i=head[k];i;i=edge[i].nxt)
{
int v=edge[i].to;
if (v==father) continue;
dfs(v,k,deep+1); tot[k]+=tot[v];
if (bigson<tot[v])
{
bigson=tot[v]; son[k]=v;
}
}
}
void dfs(int k,int tp)
{
idx[k]=++cnt; top[k]=tp;
if (!son[k]) return; dfs(son[k],tp);
for (reg int i=head[k];i;i=edge[i].nxt)
{
int v=edge[i].to;
if (!idx[v]) dfs(v,v);
}
}
inline void pushup(int now)
{
maxn[now]=max(maxn[now<<1],maxn[now<<1|1]);
}
inline void pushdown(int now)
{
if (tag[now]!=-1)
{
maxn[now<<1]=maxn[now<<1|1]=tag[now];
tag[now<<1]=tag[now<<1|1]=tag[now];
lazy[now<<1]=lazy[now<<1|1]=0;
tag[now]=-1;
}
if (lazy[now])
{
lazy[now<<1]+=lazy[now];
lazy[now<<1|1]+=lazy[now];
maxn[now<<1]+=lazy[now];
maxn[now<<1|1]+=lazy[now];
lazy[now]=0;
}
}
void build(int l,int r,int now)
{
lazy[now]=0; tag[now]=-1;
if (l==r)
{
maxn[now]=w[l]; return;
}
int mid=(l+r)>>1;
build(l,mid,now<<1);
build(mid+1,r,now<<1|1);
pushup(now);
}
void outchange(int p,int l,int r,int now,int c)
{
if (l==r)
{
maxn[now]=c; return;
}
int mid=(l+r)>>1; pushdown(now);
if (p<=mid) outchange(p,l,mid,now<<1,c);
else outchange(p,mid+1,r,now<<1|1,c);
pushup(now);
}
void inchange(int L,int R,int l,int r,int now,int c)//都修改为一个数
{
if (l>R||r<L) return;
if (l>=L&&r<=R)
{
maxn[now]=c; tag[now]=c;
lazy[now]=0; return;
}
int mid=(l+r)>>1; pushdown(now);
if (mid>=R) inchange(L,R,l,mid,now<<1,c);
else if (mid<L) inchange(L,R,mid+1,r,now<<1|1,c);
else
{
inchange(L,mid,l,mid,now<<1,c);
inchange(mid+1,R,mid+1,r,now<<1|1,c);
}
pushup(now);
}
void inchanges(int L,int R,int l,int r,int now,int c)//都加上一个数
{
if (l>R||r<L) return;
if (l>=L&&r<=R)
{
maxn[now]+=c; lazy[now]+=c; return;
}
int mid=(l+r)>>1; pushdown(now);
if (mid>=R) inchanges(L,R,l,mid,now<<1,c);
else if (mid<L) inchanges(L,R,mid+1,r,now<<1|1,c);
else
{
inchanges(L,mid,l,mid,now<<1,c);
inchanges(mid+1,R,mid+1,r,now<<1|1,c);
}
pushup(now);
}
int getmax(int L,int R,int l,int r,int now)
{
if (l>R||r<L) return -1e9;
if (l>=L&&r<=R) return maxn[now];
int mid=(l+r)>>1; pushdown(now);
if (mid>=R) return getmax(L,R,l,mid,now<<1);
if (mid<L) return getmax(L,R,mid+1,r,now<<1|1);
return max(getmax(L,mid,l,mid,now<<1),getmax(mid+1,R,mid+1,r,now<<1|1));
}
inline void treechange(int x,int y,int val)//都修改为一个数
{
while (top[x]!=top[y])
{
if (dep[top[x]]<dep[top[y]]) swap(x,y);
inchange(idx[top[x]],idx[x],1,n,1,val);
x=fa[top[x]];
}
if (dep[x]>dep[y]) swap(x,y);
inchange(idx[x]+1,idx[y],1,n,1,val);
}
inline void treechanges(int x,int y,int val)//都加上一个数
{
while (top[x]!=top[y])
{
if (dep[top[x]]<dep[top[y]]) swap(x,y);
inchanges(idx[top[x]],idx[x],1,n,1,val);
x=fa[top[x]];
}
if (dep[x]>dep[y]) swap(x,y);
inchanges(idx[x]+1,idx[y],1,n,1,val);
}
inline int treemax(int x,int y)
{
int ans=-1e9;
while (top[x]!=top[y])
{
if (dep[top[x]]<dep[top[y]]) swap(x,y);
ans=max(ans,getmax(idx[top[x]],idx[x],1,n,1));
x=fa[top[x]];
}
if (dep[x]>dep[y]) swap(x,y);
return max(ans,getmax(idx[x]+1,idx[y],1,n,1));
}
int main()
{
n=read();
for (reg int i=1;i<n;i++)
{
int x=read(),y=read(),z=read();
add_edge(x,y,z);
add_edge(y,x,z);
}
dfs(1,0,1); dfs(1,1);
for (reg int i=1;i<=num;i+=2)
{
int &u=edge[i].from,&v=edge[i].to;
if (dep[u]>dep[v]) swap(u,v);
w[idx[v]]=edge[i].dis;
}
build(1,n,1);
while (1)
{
char opt[10]; scanf("%s",opt);
if (opt[0]=='S') break;
int x=read(),y=read();
if (opt[0]=='C')
if (opt[1]=='h') outchange(idx[edge[(x<<1)-1].to],1,n,1,y);
else treechange(x,y,read());
if (opt[0]=='A') treechanges(x,y,read());
if (opt[0]=='M') printf("%d\n",treemax(x,y));
}
return 0;
}
```