洛谷 P1505 旅游 题解 【树链剖分】【线段树】
点击量：286
是一个对边剖分的树剖题。
题目描述
Ray 乐忠于旅游，这次他来到了 T 城。T 城是一个水上城市，一共有\(N\)个景点，有些景点之间会用一座桥连接。为了方便游客到达每个景点但又为了节约成本，T 城的任意两个景点之间有且只有一条路径。换句话说， T 城中只有\(N-1\)座桥。
Ray 发现，有些桥上可以看到美丽的景色，让人心情愉悦，但有些桥狭窄泥泞，令人烦躁。于是，他给每座桥定义一个愉悦度\(w\)，也就是说，Ray 经过这座桥会增加\(w\)的愉悦度，这或许是正的也可能是负的。有时，Ray 看待同一座桥的心情也会发生改变。
现在，Ray 想让你帮他计算从\(u\)景点到\(v\)景点能获得的总愉悦度。有时，他还想知道某段路上最美丽的桥所提供的最大愉悦度，或是某段路上最糟糕的一座桥提供的最低愉悦度。
输入输出格式
输入格式：
输入的第一行包含一个整数\(N\)，表示 T 城中的景点个数。景点编号为\(0\dots N-1\)。
接下来\(N-1\)行，每行三个整数\(u\)、\(v\)和\(w\)，表示有一条\(u\)到\(v\)，使 Ray 愉悦度增加\(w\)的桥。桥的编号为\(1\dots N-1\)。\(|w|\le 1000\)。 输入的第N + 1 行包含一个整数M，表示Ray 的操作数目。
接下来有\(M\)行，每行描述了一个操作，操作有如下五种形式：
C i w，表示 Ray 对于经过第\(i\)座桥的愉悦度变成了\(w\)。
N u v，表示 Ray 对于经过景点\(u\)到\(v\)的路径上的每一座桥的愉悦度都变成原来的相反数。
SUM u v，表示询问从景点\(u\)到\(v\)所获得的总愉悦度。
MAX u v，表示询问从景点\(u\)到\(v\)的路径上的所有桥中某一座桥所提供的最大愉悦度。
MIN u v，表示询问从景点u 到v 的路径上的所有桥中某一座桥所提供的最小愉悦度。测试数据保证，任意时刻，Ray 对于经过每一座桥的愉悦度的绝对值小于等于\(1000\)。
输出格式：
对于每一个询问(操作
S、MAX和MIN)，输出答案。输入输出样例
输入样例#1：3 0 1 1 1 2 2 8 SUM 0 2 MAX 0 2 N 0 1 SUM 0 2 MIN 0 2 C 1 3 SUM 0 2 MAX 0 2输出样例#1：3 2 1 -1 5 3
题解：
以前总觉得维护边比维护点难，实际上只要咕忽略掉LCA就可以了。
因为只有单点修改，所以单次时间复杂度严格\(O(\log n)\)，直接修改，不用\(\mathrm{lazytag}\)。而区间反转需要\(\mathrm{lazytag}\)，因此一共只需要维护一个\(\mathrm{lazytag}\)。
维护边上信息要求每个点维护它的父亲边，因为只有父亲边是唯一的，根节点不维护。不过单点修改需要注意调用\(dfn\)，而且要预处理出这条边是哪个点的父亲边。剩下的部分包括线段树和普通树剖一样。
查询时需要分三种情况，统计答案的方式是不同的。在跳到最后\(top[u]=top[v]\)时，要把深度较浅的（即LCA）忽略掉。当\(u=v\)时直接返回，否则在闭区间\([dfn[较浅的点]+1,dfn[较深的点]]\)中统计答案。
Code：
一不小心写了
#include<cstdio>
#include<cstring>
#define ls (k<<1)
#define rs (k<<1|1)
#define mid ((l+r)>>1)
#define inf 0x3fffffff
#define N 100100
int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
int Max(int x,int y)
{
return x>y?x:y;
}
int Min(int x,int y)
{
return x<y?x:y;
}
int a[N];//下标是dfn
struct node
{
int l,r,mx,mn,v;
bool lazy;
node(int l,int r)
{
this->l=l;
this->r=r;
lazy=0;
}
node(){}
}t[N<<2];
void pushup(int k)
{
t[k].mx=Max(t[ls].mx,t[rs].mx);
t[k].mn=Min(t[ls].mn,t[rs].mn);
t[k].v=t[ls].v+t[rs].v;
}
void build(int k,int l,int r)
{
t[k]=node(l,r);
if(l==r)
{
t[k].mx=a[l];
t[k].mn=a[l];
t[k].v=a[l];
return;
}
build(ls,l,mid);
build(rs,mid+1,r);
pushup(k);
return;
}
void pushdown(int k)
{
if(!t[k].lazy||t[k].l==t[k].r)
return;
t[k].lazy=0;
int tmp=t[ls].mx;
t[ls].mx=-t[ls].mn;
t[ls].mn=-tmp;
t[ls].v=-t[ls].v;
t[ls].lazy^=1;
tmp=t[rs].mx;
t[rs].mx=-t[rs].mn;
t[rs].mn=-tmp;
t[rs].v=-t[rs].v;
t[rs].lazy^=1;
return;
}
void contr(int k,int l,int r)//取反
{
if(r<t[k].l||l>t[k].r)
return;
if(l<=t[k].l&&r>=t[k].r)
{
int tmp=t[k].mx;
t[k].mx=-t[k].mn;
t[k].mn=-tmp;
t[k].v=-t[k].v;
t[k].lazy^=1;
return;
}
pushdown(k);
contr(ls,l,r);
contr(rs,l,r);
pushup(k);
return;
}
void change(int k,int p,int x)
{
if(t[k].l==t[k].r)
{
t[k].mn=x;
t[k].mx=x;
t[k].v=x;
return;
}
pushdown(k);
int Mid=(t[k].l+t[k].r)>>1;
if(p<=Mid)
change(ls,p,x);
else
change(rs,p,x);
pushup(k);
}
int ask(int k,int l,int r,int ty)
{
if(r<t[k].l||l>t[k].r)
{
if(ty==1)//最大值
return -inf;
else if(ty==2)//最小值
return inf;
else
return 0;
}
if(l<=t[k].l&&r>=t[k].r)
{
if(ty==1)
return t[k].mx;
else if(ty==2)
return t[k].mn;
else
return t[k].v;
}
pushdown(k);
if(ty==1)
return Max(ask(ls,l,r,1),ask(rs,l,r,1));
if(ty==2)
return Min(ask(ls,l,r,2),ask(rs,l,r,2));
return ask(ls,l,r,3)+ask(rs,l,r,3);
}
struct edge
{
int n,nxt,v,id;
edge(int n,int nxt,int v,int id)
{
this->n=n;
this->nxt=nxt;
this->v=v;
this->id=id;
}
edge(){}
}e[N<<1];
int head[N],ecnt=-1;
void add(int from,int to,int v,int id)
{
e[++ecnt]=edge(to,head[from],v,id);
head[from]=ecnt;
e[++ecnt]=edge(from,head[to],v,id);
head[to]=ecnt;
}
int sz[N],d[N],tp[N],fa[N],son[N],dfn[N],pnt[N],dcnt=0;
//pnt表示这条边归谁管
void dfs1(int x)
{
sz[x]=1;
for(int i=head[x];~i;i=e[i].nxt)
if(e[i].n!=fa[x])
{
d[e[i].n]=d[x]+1;
fa[e[i].n]=x;
dfs1(e[i].n);
son[x]=(son[x]==-1||sz[e[son[x]].n]>sz[e[i].n])?son[x]:e[i].n;
sz[x]+=sz[e[i].n];
}
}
void dfs2(int x,int t)
{
tp[x]=t;
dfn[x]=++dcnt;
if(~son[x])
{
int s=son[x];
dfs2(e[s].n,t);
a[dfn[e[s].n]]=e[s].v;
pnt[e[s].id]=son[x];
}
for(int i=head[x];~i;i=e[i].nxt)
if(e[i].n!=son[x]&&e[i].n!=fa[x])
{
dfs2(e[i].n,e[i].n);
a[dfn[e[i].n]]=e[i].v;
pnt[e[i].id]=e[i].n;
}
}
void modify(int u,int v)
{
int tu=tp[u],tv=tp[v];
while(tu!=tv)
{
if(d[tu]<d[tv])
{
contr(1,dfn[tv],dfn[v]);
v=fa[tv];
tv=tp[v];
}
else
{
contr(1,dfn[tu],dfn[u]);
u=fa[tu];
tu=tp[u];
}
}
if(u==v)
return;
if(d[u]<d[v])
contr(1,dfn[v]+1,dfn[u]);
else
contr(1,dfn[u]+1,dfn[v]);
}
int ask(int u,int v,int ty)
{
int tu=tp[u],tv=tp[v],ans;
if(ty==1)
ans=-inf;
else if(ty==2)
ans=inf;
else
ans=0;
while(tu!=tv)
{
if(d[tu]<d[tv])
{
if(ty==1)
ans=Max(ans,ask(1,dfn[tv],dfn[v],1));
else if(ty==2)
ans=Min(ans,ask(1,dfn[tv],dfn[v],2));
else
ans+=ask(1,dfn[tv],dfn[v],3);
v=fa[tv];
tv=tp[v];
}
else
{
if(ty==1)
ans=Max(ans,ask(1,dfn[tu],dfn[u],1));
else if(ty==2)
ans=Min(ans,ask(1,dfn[tu],dfn[u],2));
else
ans+=ask(1,dfn[tu],dfn[u],3);
u=fa[tu];
tu=tp[u];
}
}
if(u==v)
return ans;
if(d[u]<d[v])
{
int tt=u;
u=v;
v=tt;
}
if(ty==1)
return Max(ans,ask(1,dfn[u]+1,dfn[v],1));
else if(ty==2)
return Min(ans,ask(1,dfn[u]+1,dfn[v],2));
else
return ans+ask(1,dfn[u]+1,dfn[v],3);
}
char op[1000];
int main()
{
memset(head,-1,sizeof(head));
memset(son,-1,sizeof(son));
int n,u,v,w;
n=read();
for(int i=1;i<n;++i)
{
u=read();
v=read();
w=read();
add(u,v,w,i);
}
d[0]=1;
dfs1(0);
dfs2(0,0);
build(1,1,n);
int m=read();
for(int i=1;i<=m;++i)
{
scanf("%s",op);
u=read();
v=read();
if(op[0]=='C')
change(1,dfn[pnt[u]],v);
else if(op[0]=='N')
modify(u,v);
else if(op[0]=='S')
printf("%d\n",ask(u,v,3));
else if(op[1]=='A')
printf("%d\n",ask(u,v,1));
else
printf("%d\n",ask(u,v,2));
}
return 0;
}
说点什么