[SDOI2014]旅行解题报告

题目描述

S国有N个城市，编号从1到N。城市间用N-1条双向道路连接，满足从一个城市出发可以到达其它所有城市。每个城市信仰不同的宗教，如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰。

为了方便，我们用不同的正整数代表各种宗教， S国的居民常常旅行。旅行时他们总会走最短路，并且为了避免麻烦，只在信仰和他们相同的城市留宿。当然旅程的终点也是信仰与他相同的城市。S国政府为每个城市标定了不同的旅行评级，旅行者们常会记下途中（包括起点和终点）留宿过的城市的评级总和或最大值。

在S国的历史上常会发生以下几种事件：

“CC x c“：城市x的居民全体改信了c教；

“CW x w“：城市x的评级调整为w;

“QS x y“：一位旅行者从城市x出发，到城市y，并记下了途中留宿过的城市的评级总和；

“QM x y“：一位旅行者从城市x出发，到城市y，并记下了途中留宿过的城市的评级最大值。

由于年代久远，旅行者记下的数字已经遗失了，但记录开始之前每座城市的信仰与评级，还有事件记录本身是完好的。请根据这些信息，还原旅行者记下的数字。为了方便，我们认为事件之间的间隔足够长，以致在任意一次旅行中，所有城市的评级和信仰保持不变。

　　　　　　　　　　　　　　　　　　　　--by luogu

http://daniu.luogu.org/problem/show?pid=3313

得到模型——询问树上两点间路径中符合条件的点的加和与最值，支持单点修改权值和条件；

考虑建立C（宗教数）棵线段树——然后内存显然不够，

但可以不把她们开满：

如对于宗教i所属的线段树，只有属于宗教i的叶节点以及其祖先结构被建立；

相当于每个叶节点连一条向相应根的树链；

于是c棵线段树等价于n-条树链；

nlogn级内存；

对于每次宗教修改：

把原树上该点的权值清零，在该点的新宗教的树中建一条通向她的树链，为了方便下次修改，记得把原数组中的宗教值修改；

对于每次权值修改：

直接修改即可；

一个优化：

每次修改时动态的把已经为零的树链断开；

这样貌似可以减小查询的常数（因为当查询到不存在的树链时会直接返回）

然而实际评测时发现仿佛没什么用

代码如下：（精简而合适的代码）

 #include<cstdio>

 #include<cstring>

 const int MAXN=;

 int n,m,L,R;

 int reli[MAXN],dis[MAXN],dep[MAXN],size[MAXN],fa[MAXN],hine[MAXN],rank[MAXN],top[MAXN],a[MAXN];

 struct pool{

     int sum,ls,rs,max;

 }data[MAXN*];

 int tot;

 int root[MAXN];

 struct ss{

     int next,to;

 }e[MAXN<<];

 int first[MAXN],num;

 void swap(int& a,int& b){int i=a;a=b;b=i;}

 void Init();

 void build(int ,int );

 void dfs_1(int );

 void dfs_2(int ,int );

 void work();

 void chan_reli(int ,int );

 void chan_sum(int ,int );

 void get(int ,int ,int );

 void up(int );

 void builine(int ,int ,int&,int ,int );

 int g_sum(int ,int ,int );

 int g_max(int ,int ,int );

 int main()

 {

     Init();

     work();

     return ;

 }

 void Init(){

     int i,j,k;

     memset(dep,,sizeof(dep));

     memset(size,,sizeof(size));

     scanf("%d%d",&n,&m);

     for(i=;i<=n;i++)

         scanf("%d%d",&dis[i],&reli[i]);

     for(i=;i<n;i++){

         hine[i]=i;

         scanf("%d%d",&j,&k);

         build(j,k);build(k,j);

     }

     hine[n]=n;dep[]=;

     dfs_1();num=;

     dfs_2(,);num=;

     for(i=;i<=n;i++)

         builine(,n,root[reli[a[i]]],i,dis[a[i]]);

 }

 void build(int f,int t){

     e[++num].next=first[f];

     e[num].to=t;

     first[f]=num;

 }

 void dfs_1(int now){

     int i;

     for(i=first[now];i;i=e[i].next)

         if(!dep[e[i].to]){

             dep[e[i].to]=dep[now]+;

             fa[e[i].to]=now;

             dfs_1(e[i].to);

             size[now]+=size[e[i].to];

             if(hine[now]==now||size[e[i].to]>size[hine[now]])

                 hine[now]=e[i].to;

         }

     size[now]++;

 }

 void dfs_2(int now,int now_top){

     int i;

     top[now]=now_top;

     rank[now]=++num;

     a[num]=now;

     if(hine[now]!=now)

         dfs_2(hine[now],now_top);

     for(i=first[now];i;i=e[i].next)

         if(dep[e[i].to]==dep[now]+&&e[i].to!=hine[now])

             dfs_2(e[i].to,e[i].to);

 }

 void work(){

     int i,j,k,u,v;

     char s[];

     for(i=;i<=m;i++){

         scanf("%s%d%d",s,&u,&v);

         switch(s[]){

             case 'C':chan_reli(u,v);break;

             case 'W':chan_sum(u,v);break;

             case 'S':get(u,v,);break;

             case 'M':get(u,v,);break;

         }

     }

 }

 void chan_reli(int u,int v){

     builine(,n,root[v],rank[u],dis[u]);

     builine(,n,root[reli[u]],rank[u],);

     reli[u]=v;

 }

 void chan_sum(int u,int v){

     builine(,n,root[reli[u]],rank[u],v);

     dis[u]=v;

 }

 void get(int u,int v,int kind){

     int ans=,ro=root[reli[u]],i,j,k;

     while(top[u]!=top[v]){

         if(dep[top[u]]>dep[top[v]]){

             L=rank[top[u]];R=rank[u];

             u=fa[top[u]];

         }

         else{

             L=rank[top[v]];R=rank[v];

             v=fa[top[v]];

         }

         if(!kind)

             ans+=g_sum(,n,ro);

         else{

             i=g_max(,n,ro);

             if(i>ans)ans=i;

         }

     }

     if(dep[u]>dep[v]){

         swap(u,v);

     }

     L=rank[u];R=rank[v];

     if(!kind)

         ans+=g_sum(,n,ro);

     else{

         i=g_max(,n,ro);

         if(i>ans)ans=i;

     }

     printf("%d\n",ans);

 }

 void up(int nu){

     data[nu].sum=data[data[nu].ls].sum+data[data[nu].rs].sum;

     data[nu].max=data[data[nu].ls].max>data[data[nu].rs].max?data[data[nu].ls].max:data[data[nu].rs].max;

 }

 void builine(int l,int r,int&now,int x,int sum){

     if(!now){

         now=++tot;

     }

     if(l==r){

         data[now].sum=sum;

         data[now].max=sum;

         return ;

     }

     int mid=(l+r)>>;

     if(x<=mid)

         builine(l,mid,data[now].ls,x,sum);

     else

         builine(mid+,r,data[now].rs,x,sum);

     up(now);

     if(!data[now].sum)now=;

 }

 int g_sum(int l,int r,int now){

     if(!now)

         return ;

     if(L<=l&&r<=R)

         return data[now].sum;

     int mid=(l+r)>>,ans=;

     if(L<=mid)

         ans+=g_sum(l,mid,data[now].ls);

     if(R>mid)

         ans+=g_sum(mid+,r,data[now].rs);

     return ans;

 }

 int g_max(int l,int r,int now){

     if(!now)

         return ;

     if(L<=l&&r<=R)

         return data[now].max;

     int mid=(l+r)>>,lm=,rm=;

     if(L<=mid)

         lm=g_max(l,mid,data[now].ls);

     if(R>mid)

         rm=g_max(mid+,r,data[now].rs);

     if(lm>=rm)

         return lm;

     return rm;

 }

祝AC

巴特西

[SDOI2014]旅行解题报告

题目描述

最新文章

热门文章