注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ1984]月下“毛景树”  

2015-06-20 15:22:29|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1984: 月下“毛景树”

Time Limit: 20 Sec  Memory Limit: 64 MB
Submit: 1022  Solved: 334
[Submit][Status][Discuss]

Description

毛毛虫经过及时的变形,最终逃过的一劫,离开了菜妈的菜园。 毛毛虫经过千山万水,历尽千辛万苦,最后来到了小小的绍兴一中的校园里。爬啊爬~爬啊爬~~毛毛虫爬到了一颗小小的“毛景树”下面,发现树上长着他最爱吃的毛毛果~~~ “毛景树”上有N个节点和N-1条树枝,但节点上是没有毛毛果的,毛毛果都是长在树枝上的。但是这棵“毛景树”有着神奇的魔力,他能改变树枝上毛毛果的个数: ? Change k w:将第k条树枝上毛毛果的个数改变为w个。 ? Cover u v w:将节点u与节点v之间的树枝上毛毛果的个数都改变为w个。 ? Add u v w:将节点u与节点v之间的树枝上毛毛果的个数都增加w个。 由于毛毛虫很贪,于是他会有如下询问: ? Max u v:询问节点u与节点v之间树枝上毛毛果个数最多有多少个。

Input

第一行一个正整数N。 接下来N-1行,每行三个正整数Ui,Vi和Wi,第i+1行描述第i条树枝。表示第i条树枝连接节点Ui和节点Vi,树枝上有Wi个毛毛果。 接下来是操作和询问,以“Stop”结束。

Output

对于毛毛虫的每个询问操作,输出一个答案。

Sample Input

4 1 2 8 1 3 7 3 4 9 Max 2 4 Cover 2 4 5 Add 1 4 10 Change 1 16 Max 2 4 Stop

Sample Output

9 16 【Data Range】 1<=N<=100,000,操作+询问数目不超过100,000。 保证在任意时刻,所有树枝上毛毛果的个数都不会超过10^9个。

Solution

树链剖分||LCT
时刻要注意不能把标记传到null上!!!

Code

//我只是来秀代码长度的
/**************************************************************
    Problem: 1984
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:5648 ms
    Memory:10768 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
char ch,B[1<<15],*S=B,*T=B,op;
#define getc() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++)
int aa;int F(){
    while(ch=getc(),ch<'0'||ch>'9');aa=ch-'0';
    while(ch=getc(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return aa;
}
#define N 200010
int rev[N],son[N][2],fa[N],set[N],add[N],max[N],val[N],n,e[N][2],st,x,y,v,i;
#define swap(a,b) (st=a,a=b,b=st)
#define cmax(a,b) (a<b?a=b:1)
#define nr(t) (son[fa[t]][0]==t||son[fa[t]][1]==t)
#define ls son[t][0]
#define rs son[t][1]
void pu(int t){
    max[t]=val[t],cmax(max[t],max[ls]),cmax(max[t],max[rs]);
}
void rtt(int t){
    int f=fa[t],p=son[f][1]==t;
    fa[t]=fa[f],nr(f)?son[fa[f]][son[fa[f]][1]==f]=t:1,
    (son[f][p]=son[t][!p])?fa[son[f][p]]=f:1,pu(son[fa[f]=t][!p]=f);
}
void pv(int t){
    if(nr(t))pv(fa[t]);
    if(rev[t])rev[t]=0,rev[ls]^=1,rev[rs]^=1,swap(ls,rs);
    if(~set[t]){
        if(ls)max[ls]=set[ls]=set[t];
        if(rs)max[rs]=set[rs]=set[t];
        val[ls]=ls>n?set[t]:0,val[rs]=rs>n?set[t]:0,
        add[ls]=add[rs]=0,set[t]=-1;
    }
    if(add[t]){
        if(ls)add[ls]+=add[t],max[ls]+=add[t];
        if(rs)add[rs]+=add[t],max[rs]+=add[t];
        ls>n?val[ls]+=add[t]:val[ls]=0;
        rs>n?val[rs]+=add[t]:val[rs]=0;add[t]=0;
    }
}
void splay(int t){int f;
    for(pv(t);nr(t);rtt(t))
    if(f=fa[t],nr(f))rtt(son[f][1]==t^son[fa[f]][1]==f?t:f);pu(t);
}
void access(int t){
    for(int las=0;t;splay(t),rs=las,las=t,t=fa[t]);
}
#define mkr(t) (access(t),splay(t),rev[t]^=1)
#define gr(x,y) (mkr(x),access(y),splay(y))
#define link(x,y) (mkr(x),fa[x]=y)
#define cut(x,y) (gr(x,y),fa[x]=son[y][0]=0)
char getop(){
    while(op=getc(),op<'A'||op>'Z');return op=getc();
}
int main(){
    for(memset(set,-1,sizeof(set)),n=F(),i=1;i<n;i++)
    e[i][0]=x=F(),e[i][1]=y=F(),val[i+n]=F(),link(x,i+n),link(i+n,y);
    while(getop()!='t')
    if(op=='h')i=F(),x=e[i][0],y=e[i][1],v=F(),gr(x,y),set[y]=max[y]=v,add[y]=0;
    else if(op=='o')x=F(),y=F(),v=F(),gr(x,y),set[y]=max[y]=v,add[y]=0;
    else if(op=='d')x=F(),y=F(),v=F(),gr(x,y),max[y]+=v,add[y]+=v;
    else x=F(),y=F(),gr(x,y),printf("%d\n",max[y]);
}
  评论这张
 
阅读(15)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018