【BZOJ 3531】 [Sdoi2014]旅行

2015-04-14 为码而活 PHP教程 关注408次 已收录
当前位置：波比源码 > 【BZOJ 3531】 [Sdoi2014]旅行
正文概述

3531: [Sdoi2014]旅行

Time Limit: 20 Sec Memory Limit: 512 MB
Submit: 575 Solved: 303
[Submit][Status][Discuss]
Description

S国有N个城市，编号从1到N。城市间用N⑴条双向道路连接，满足
从1个城市动身可以到达其它所有城市。每一个城市信仰不同的宗教，如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰。为了方便，我们用不同的正整数代表各种宗教， S国的居民常常旅行。旅行时他们总会走最短路，并且为了不麻烦，只在信仰和他们相同的城市留宿。固然旅程的终点也是信仰与他相同的城市。S国政府为每一个城市标定了不同的旅行评级，旅行者们常会记下途中（包括出发点和终点）留宿过的城市的评级总和或最大值。
在S国的历史上常会产生以下几种事件：
”CC x c”：城市x的居民全部改信了c教；
”CW x w”：城市x的评级调剂为w;
”QS x y”：1位旅行者从城市x动身，到城市y，并记下了途中留宿过的城市的评级总和；
”QM x y”：1位旅行者从城市x动身，到城市y，并记下了途中留宿过
的城市的评级最大值。
由于年代久远，旅行者记下的数字已遗失了，但记录开始之前每座城市的信仰与评级，还有事件记录本身是完好的。请根据这些信息，还原旅行者记下的数字。 为了方便，我们认为事件之间的间隔足够长，以致在任意1次旅行中，所有城市的评级和信仰保持不变。

Input

输入的第1行包括整数N，Q顺次表示城市数和事件数。
接下来N行，第i+l行两个整数Wi，Ci顺次表示记录开始之前，城市i的

评级和信仰。
接下来N⑴行每行两个整数x，y表示1条双向道路。
接下来Q行，每行1个操作，格式如上所述。

Output

对每一个QS和QM事件，输出1行，表示旅行者记下的数字。

Sample Input

5 6

3 1

2 3

1 2

3 3

5 1

1 2

1 3

3 4

3 5

QS 1 5

CC 3 1

QS 1 5

CW 3 3

QS 1 5

QM 2 4

Sample Output

8

9

11

3

HINT

N，Q < =10^5 ， C < =10^5

数据保证对所有QS和QM事件，出发点和终点城市的信仰相同；在任意时

刻，城市的评级总是不大于10^4的正整数，且宗教值不大于C。

Source

Round 1 Day 1

树链剖分+动态开结点。

如果没有同1个信仰的限制就是裸的树链剖分了。

我们可以对每个信仰都建1棵线段树，但是普通方法建线段树就会MLE。

因此我们采取动态开结点的办法：
假定n=5,我们要在线段树中加入1个id=4的人，那末我们只需要开”4⑸”这个结点，而不用开”1⑶”的结点，由于开了也没用。

在最坏情况下，每一个人都属于不同的信仰，我们对每一个信仰开1棵线段树，也只需要nlogn个节点了~

然后就是裸的树链剖分了。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#define M 100005
using namespace std;
int id[M],n,now,q,h[M],tote=0,tot=0,fa[M],size[M],son[M],dep[M],top[M];
int root[M];
struct data
{
int c,w;
}a[M];
struct Segtree
{
int l,r,ma,sum;
}t[8000005];
struct edge
{
int y,ne;
}e[M*2];
void Addedge(int x,int y)
{
e[++tote].y=y;
e[tote].ne=h[x];
h[x]=tote;
}
void dfs1(int x,int f,int de)
{
dep[x]=de;
size[x]=1;
son[x]=0;
fa[x]=f;
for (int i=h[x];i;i=e[i].ne)
{
int y=e[i].y;
if (y==f) continue;
dfs1(y,x,de+1);
size[x]+=size[y];
if (size[son[x]]<size[y])
son[x]=y;
}
}
void dfs2(int x,int tp)
{
top[x]=tp;
id[x]=++now;
if (son[x]) dfs2(son[x],tp);
for (int i=h[x];i;i=e[i].ne)
{
int y=e[i].y;
if (y==son[x]||y==fa[x]) continue;
dfs2(y,y);
}
}
void Push_up(int x)
{
t[x].ma=max(t[t[x].l].ma,t[t[x].r].ma);
t[x].sum=t[t[x].l].sum+t[t[x].r].sum;
}
void Build(int &x,int l,int r,int p,int v)
{
if (!x) x=++tot;
if (l==r)
{
t[x].sum=t[x].ma=v;
return;
}
int m=(l+r)>>1;
if (p<=m) Build(t[x].l,l,m,p,v);
else Build(t[x].r,m+1,r,p,v);
Push_up(x);
}
int Getsum(int x,int lt,int rt,int l,int r)
{
if (!x) return 0;
if (l<=lt&&rt<=r) return t[x].sum;
int m=(lt+rt)>>1;
int ans=0;
if (l<=m) ans+=Getsum(t[x].l,lt,m,l,r);
if (r>m) ans+=Getsum(t[x].r,m+1,rt,l,r);
return ans;
}
int Qsum(int x,int y)
{
int C=a[x].c;
int tp1=top[x],tp2=top[y];
int ans=0;
while (tp1!=tp2)
{
if (dep[tp1]<dep[tp2])
swap(tp1,tp2),swap(x,y);
ans+=Getsum(root[C],1,n,id[tp1],id[x]);
x=fa[tp1];
tp1=top[x];
}
if (x==y) return ans+(a[x].c==C)*a[x].w;
if (dep[x]>dep[y]) swap(x,y);
ans+=Getsum(root[C],1,n,id[x],id[y]);
return ans;
}
int Getmax(int x,int lt,int rt,int l,int r)
{
if (!x) return 0;
if (l<=lt&&rt<=r) return t[x].ma;
int m=(lt+rt)>>1;
int ans=0;
if (l<=m) ans=Getmax(t[x].l,lt,m,l,r);
if (r>m) ans=max(ans,Getmax(t[x].r,m+1,rt,l,r));
return ans;
}
int Qmax(int x,int y)
{
int C=a[x].c;
int tp1=top[x],tp2=top[y];
int ans=0;
while (tp1!=tp2)
{
if (dep[tp1]<dep[tp2])
swap(tp1,tp2),swap(x,y);
ans=max(ans,Getmax(root[C],1,n,id[tp1],id[x]));
x=fa[tp1];
tp1=top[x];
}
if (x==y) return max(ans,(a[x].c==C)*a[x].w);
if (dep[x]>dep[y]) swap(x,y);
ans=max(ans,Getmax(root[C],1,n,id[x],id[y]));
return ans;
}
int main()
{
now=0;
scanf("%d%d",&n,&q);
for (int i=1;i<=n;i++)
scanf("%d%d",&a[i].w,&a[i].c);
for (int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
Addedge(x,y);
Addedge(y,x);
}
dfs1(1,0,1);
dfs2(1,0);
for (int i=1;i<=n;i++)
Build(root[a[i].c],1,n,id[i],a[i].w);
while (q--)
{
char s[5];
int x,y;
scanf("%s",s);
scanf("%d%d",&x,&y);
if (s[0]=='C')
{
if (s[1]=='C')
{
Build(root[a[x].c],1,n,id[x],0);
a[x].c=y;
Build(root[a[x].c],1,n,id[x],a[x].w);
}
else
{
a[x].w=y;
Build(root[a[x].c],1,n,id[x],a[x].w);
}
}
else
{
if (s[1]=='S')
printf("%d
",Qsum(x,y));
else printf("%d
",Qmax(x,y));
}
}
return 0;
}

这里写图片描述
感悟：
这道题调了好久，由于树链剖分返回的时候没有判断最后1个点是不是是与出发点属于同1个信仰的。。

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！
2. 分享目的仅供大家学习和交流，您必须在下载后24小时内删除！
3. 不得使用于非法商业用途，不得违反国家法律。否则后果自负！
4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！
5. 如有链接无法下载、失效或广告，请联系管理员处理！
6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！
7. 本站源码并不保证全部能正常使用，仅供有技术基础的人学习研究，请谨慎下载
8. 如遇到加密压缩包，请使用WINRAR解压,如遇到无法解压的请联系管理员！

波比源码 » 【BZOJ 3531】 [Sdoi2014]旅行
分享到：

76 评论

  8. order tadalis online cheap tadacip 10mg tablet order diclofenac 100mg for sale

  20. cialis 20mg cost cialis 5mg us buy amantadine 100 mg pill

  21. order avlosulfon 100mg pills aceon medication order perindopril 8mg without prescription

  23. provigil 100mg for sale stromectol pills ivermectin 3mg tablets price

  32. order metoprolol 50mg without prescription buy levitra generic vardenafil order online

  36. priligy 60mg without prescription priligy 30mg cheap order synthroid 150mcg pills

  40. lioresal drug zanaflex uk toradol 10mg drug

  46. trazodone pills cost aurogra buy aurogra for sale

  48. sildenafil 25mg for sale estrace cheap buy lamotrigine 200mg sale

  50. buy sildenafil 50mg without prescription generic cialis 10mg tadalafil 10mg us

  54. order generic retin cream tretinoin gel tablet order avanafil 200mg without prescription

  55. lamisil pills suprax pill buy amoxicillin online cheap

  56. buy naprosyn 250mg generic naprosyn price prevacid buy online

  66. indomethacin buy online cenforce online order cenforce 50mg for sale

  68. buy tadacip without prescription tadacip cheap amoxicillin 500mg brand

  71. buy modafinil cost provigil buy generic promethazine

发表评论

Hi, 如果你对这款模板有疑问，可以跟我联系哦！

联系站长
赞助VIP 享更多特权，建议使用 QQ 登录
QQ登录
喜欢我嘛？喜欢就按“ctrl+D”收藏我吧！♡