题解 P3313 【[SDOI2014]旅行】
斯德哥尔摩
2017-12-03 12:53:36
注：此题有毒。。。
不要被标签中的 主席树 迷惑了。。。
一开始以为是 倍增LCA+主席树，于是花了 10min 敲了一发模板，然后完美地 TLE 了。。。
想了两天，无方，看题解，发现要用 树链剖分+线段树 。。。
花了半小时学习了 树剖（看完发现 树剖 是个好东东。。。），又调了半小时，终于 AC 了。。。
要点：
1.有多少个宗教，就有多少个线段树。
2.线段树需要维护两个值：区间和值，区间最值，此处 区间 由 相同宗教的城市 组成。
3.线段树除了 插入值 ，还要 删除值；当树中没有某个节点时，增加新节点，否则直接修改。
4.此处主席树应该能写，然而我不会。。。
4. 树剖 应该都会，不会的像我一样右转自行百度。。。
5.注意读入，一般都用 手写读优 。
6.注意数组大小（当初我差点就 RE 了。。。）
7.剩下的就是细节处理的问题了，什么前向星存图就不多说了，应该都没什么问题。
8.建议 max 函数手写，STL 感觉有点 慢+不靠谱 。。。
如果注意了以上还是莫名其妙地 WA 了，看代码吧。
附代码：（173行，好长。。。）
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 100010
using namespace std;
int n,m,d=1,e=1,g=1;
int c[MAXN],w[MAXN],root[MAXN];
int head[MAXN],id[MAXN],top[MAXN],deep[MAXN],fa[MAXN],son[MAXN],num[MAXN];
struct node1{//结构体前向星
int next,to;
}a[MAXN<<1];
struct node2{//动态线段树
int l,r,data1,data2;
}b[MAXN*20];
inline int read(){//弱弱的读优
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
inline int max(const int &x,const int &y){//手写 max ,感觉有点手残。。。
if(x>y)return x;
return y;
}
void pushup(int rt){//上传
b[rt].data1=b[b[rt].l].data1+b[b[rt].r].data1;
b[rt].data2=max(b[b[rt].l].data2,b[b[rt].r].data2);
}
void pushdown(int rt){//清空
b[rt].data1=b[rt].data2=b[rt].l=b[rt].r=0;
}
void insert(int k,int v,int l,int r,int &rt){//插入
int mid;
if(!rt)rt=e++;//如上 第3点
if(l==v&&v==r){
b[rt].data1=b[rt].data2=k;
return;
}
mid=l+r>>1;
if(v<=mid)insert(k,v,l,mid,b[rt].l);
else insert(k,v,mid+1,r,b[rt].r);
pushup(rt);
}
void remove(int k,int l,int r,int &rt){//删除
int mid;
if(l==r){
pushdown(rt);
rt=0;
return;
}
mid=l+r>>1;
if(k<=mid)remove(k,l,mid,b[rt].l);
else remove(k,mid+1,r,b[rt].r);
pushup(rt);
if(!b[rt].l&&!b[rt].r){//注意这里，左子树 与 右子树 都空时，节点为空
pushdown(rt);
rt=0;
}
}
int query1(int s,int t,int l,int r,int rt){//区间求和
if(!rt)return 0;//节点为空，返回
int mid;
if(l==s&&r==t)
return b[rt].data1;
mid=l+r>>1;
if(t<=mid)return query1(s,t,l,mid,b[rt].l);
else if(s>mid)return query1(s,t,mid+1,r,b[rt].r);
else return query1(s,mid,l,mid,b[rt].l)+query1(mid+1,t,mid+1,r,b[rt].r);
}
int query2(int s,int t,int l,int r,int rt){//区间求最值
if(!rt)return 0;
int mid;
if(l==s&&r==t)
return b[rt].data2;
mid=l+r>>1;
if(t<=mid)return query2(s,t,l,mid,b[rt].l);
else if(s>mid)return query2(s,t,mid+1,r,b[rt].r);
else return max(query2(s,mid,l,mid,b[rt].l),query2(mid+1,t,mid+1,r,b[rt].r));
}
void add(int x,int y){//加边
a[d].to=y;
a[d].next=head[x];
head[x]=d++;
a[d].to=x;
a[d].next=head[y];
head[y]=d++;
}
void buildtree(int rt){//建树+树剖准备1
int will;
num[rt]=1;
for(int i=head[rt];i;i=a[i].next){
will=a[i].to;
if(!deep[will]){
deep[will]=deep[rt]+1;
fa[will]=rt;
buildtree(will);
num[rt]+=num[will];
if(num[will]>num[son[rt]])son[rt]=will;
}
}
}
void dfs(int rt,int fa){//树剖准备2
if(son[rt]){
top[son[rt]]=top[rt];
id[son[rt]]=++g;
dfs(son[rt],rt);
}
int v;
for(int i=head[rt];i;i=a[i].next){
v=a[i].to;
if(v==fa||v==son[rt])continue;
top[v]=v;
id[v]=++g;
dfs(v,rt);
}
}
void change1(int x,int y){//修改宗教：原宗教中删除，新宗教中插入
remove(id[x],1,n,root[c[x]]);
c[x]=y;
insert(w[x],id[x],1,n,root[c[x]]);
}
void change2(int x,int y){//修改评价：直接插入
w[x]=y;
insert(w[x],id[x],1,n,root[c[x]]);
}
void work1(int x,int y){//求评价和
int cs=c[x],s=0;
while(top[x]!=top[y]){//树剖搞起
if(deep[top[x]]<deep[top[y]])swap(x,y);
s+=query1(id[top[x]],id[x],1,n,root[cs]);
x=fa[top[x]];
}
if(deep[x]>deep[y])swap(x,y);
s+=query1(id[x],id[y],1,n,root[cs]);//不要忘了这里。。。
printf("%d\n",s);
}
void work2(int x,int y){//求评价最值
int cs=c[x],s=0;
while(top[x]!=top[y]){//同上
if(deep[top[x]]<deep[top[y]])swap(x,y);
s=max(s,query2(id[top[x]],id[x],1,n,root[cs]));
x=fa[top[x]];
}
if(deep[x]>deep[y])swap(x,y);
s=max(s,query2(id[x],id[y],1,n,root[cs]));
printf("%d\n",s);
}
int main(){
int x,y;
char ch[3];
n=read();m=read();
for(int i=1;i<=n;i++){w[i]=read();c[i]=read();}
for(int i=1;i<n;i++){
x=read();y=read();
add(x,y);
}
deep[1]=id[1]=top[1]=1;//初值
buildtree(1);
dfs(1,0);
for(int i=1;i<=n;i++)insert(w[i],id[i],1,n,root[c[i]]);//建初始线段树
while(m--){//主过程
scanf("%s",ch);x=read();y=read();
if(ch[0]=='C'){
if(ch[1]=='C')change1(x,y);
if(ch[1]=='W')change2(x,y);
}
if(ch[0]=='Q'){
if(ch[1]=='S')work1(x,y);
if(ch[1]=='M')work2(x,y);
}
}
return 0;
}
```