| 记录编号 |
256505 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[HZOI 2015]榴莲 |
最终得分 |
100 |
| 用户昵称 |
 Aglove |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
1.674 s |
| 提交时间 |
2016-04-30 21:30:56 |
内存使用 |
23.59 MiB |
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int maxn=100010;
int n,m,mx,u,v,k;
int h[maxn],cnt=0;
struct edge{
int to,next;
}G[maxn<<1];
struct ASK{
int type;
int u,v,w,lca;
int id,la;
}Q[maxn],Q1[maxn],Q2[maxn];
int dep[maxn],fa[maxn],anc[maxn][20];
int pos[maxn],end[maxn],tot=0;
int t[maxn];
int add[maxn<<2],sum[maxn<<2];
int tmp[maxn];
int ans[maxn];
bool cmpid(const ASK &A,const ASK &B){return A.id<B.id;}
int lowbit(int x){return x&(-x);}
void BIT_UPD(int x,int v){
for(int i=x;i<=n;i+=lowbit(i))t[i]+=v;
}
int ask(int x){
int sum=0;
for(int i=x;i>=1;i-=lowbit(i))sum+=t[i];
return sum;
}
void Add(int x,int y){
++cnt;G[cnt].to=y;G[cnt].next=h[x];h[x]=cnt;
}
void push_down(int o,int A,int B){
int L=(o<<1),R=(L|1);
int mid=(A+B)>>1;
sum[L]+=(mid-A+1)*add[o];
add[L]+=add[o];
sum[R]+=(B-mid)*add[o];
add[R]+=add[o];
add[o]=0;
}
void Seg_UPD(int o,int L,int R,int x,int y,int v){
if(L>=x&&R<=y){
sum[o]+=(R-L+1)*v;
add[o]+=v;
return;
}
int mid=(L+R)>>1;
if(add[o]!=0)push_down(o,L,R);
if(y<=mid)Seg_UPD(o<<1,L,mid,x,y,v);
else if(x>mid)Seg_UPD(o<<1|1,mid+1,R,x,y,v);
else {Seg_UPD(o<<1,L,mid,x,y,v);Seg_UPD(o<<1|1,mid+1,R,x,y,v);}
sum[o]=sum[o<<1]+sum[o<<1|1];
}
int Seg_ask(int o,int L,int R,int p){
if(L==R)return sum[o];
int mid=(L+R)>>1;
if(add[o]!=0)push_down(o,L,R);
if(p<=mid)return Seg_ask(o<<1,L,mid,p);
else return Seg_ask(o<<1|1,mid+1,R,p);
}
void read(int &num){
num=0;char ch=getchar();
while(ch<'!')ch=getchar();
while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();
}
void Get_DFS(int u,int f){
anc[u][0]=f;fa[u]=f;pos[u]=++tot;
for(int i=h[u];i;i=G[i].next){
int v=G[i].to;
if(v==f)continue;
dep[v]=dep[u]+1;
Get_DFS(v,u);
}end[u]=tot;return;
}
void pre_LCA(){
for(int i=1;i<=n;++i){
for(int j=1;(1<<j)<=n;++j)anc[i][j]=-1;
}
for(int j=1;(1<<j)<=n;++j){
for(int i=1;i<=n;++i){
if(anc[i][j-1]!=-1){
int a=anc[i][j-1];
anc[i][j]=anc[a][j-1];
}
}
}return;
}
int LCA(int p,int q){
if(dep[p]<dep[q])swap(p,q);
int log;
for(log=0;(1<<log)<=dep[p];++log);--log;
for(int i=log;i>=0;--i){
if(dep[p]-(1<<i)>=dep[q])p=anc[p][i];
}
if(p==q)return p;
for(int i=log;i>=0;--i){
if(anc[p][i]!=-1&&anc[p][i]!=anc[q][i]){
p=anc[p][i];q=anc[q][i];
}
}return fa[p];
}
void Get_back(int h,int t,int mid){
for(int i=h;i<=t;++i){
if(Q[i].type==1){
if(Q[i].w>mid){
int lca=Q[i].lca;
BIT_UPD(pos[Q[i].u],-1);BIT_UPD(pos[Q[i].v],-1);
BIT_UPD(pos[lca],1);
if(fa[lca]!=-1)BIT_UPD(pos[fa[lca]],1);
}
}else if(Q[i].type==2){
if(Q[i].w>mid)Seg_UPD(1,1,n,pos[Q[i].u],end[Q[i].u],-1);
}else if(Q[i].type==3){
if(Q[i].w>mid){
if(Q[i].v){
int lca=Q[i].lca;
BIT_UPD(pos[Q[i].u],1);BIT_UPD(pos[Q[i].v],1);
BIT_UPD(pos[lca],-1);
if(fa[lca]!=-1)BIT_UPD(pos[fa[lca]],-1);
}else Seg_UPD(1,1,n,pos[Q[i].u],end[Q[i].u],1);
}
}
}return;
}
void Solve(int h,int t,int L,int R){
if(h>t)return;
if(L==R){
for(int i=h;i<=t;++i)ans[Q[i].id]=L;
return;
}
int mid=(L+R)>>1;
for(int i=h;i<=t;++i){
if(Q[i].type==1){
if(Q[i].w>mid){
int lca=Q[i].lca;
BIT_UPD(pos[Q[i].u],1);BIT_UPD(pos[Q[i].v],1);
BIT_UPD(pos[lca],-1);
if(fa[lca]!=-1)BIT_UPD(pos[fa[lca]],-1);
}
}else if(Q[i].type==2){
if(Q[i].w>mid)Seg_UPD(1,1,n,pos[Q[i].u],end[Q[i].u],1);
}else if(Q[i].type==3){
if(Q[i].w>mid){
if(Q[i].v){
int lca=Q[i].lca;
BIT_UPD(pos[Q[i].u],-1);BIT_UPD(pos[Q[i].v],-1);
BIT_UPD(pos[lca],1);
if(fa[lca]!=-1)BIT_UPD(pos[fa[lca]],1);
}else Seg_UPD(1,1,n,pos[Q[i].u],end[Q[i].u],-1);
}
}else{
int now=ask(end[Q[i].u])-ask(pos[Q[i].u]-1);
now+=Seg_ask(1,1,n,pos[Q[i].u]);
tmp[i]=now;
}
}
Get_back(h,t,mid);
int l1=0,l2=0;
for(int i=h;i<=t;++i){
if(Q[i].type!=4){
if(Q[i].w<=mid)Q1[++l1]=Q[i];
else Q2[++l2]=Q[i];
}else{
int now=tmp[i]+Q[i].la;
if(now<Q[i].w)Q[i].la+=tmp[i],Q1[++l1]=Q[i];
else Q2[++l2]=Q[i];
}
}
for(int i=1;i<=l1;++i)Q[i+h-1]=Q1[i];
for(int i=1;i<=l2;++i)Q[i+h+l1-1]=Q2[i];
Solve(h,h+l1-1,L,mid);Solve(h+l1,t,mid+1,R);
}
int main(){
freopen("Durio_zibethinus_Murr.in","r",stdin);
freopen("Durio_zibethinus_Murr.out","w",stdout);
read(n);read(m);
for(int i=1;i<n;++i){
read(u);read(v);
Add(u,v);Add(v,u);
}Get_DFS(1,-1);pre_LCA();
for(int i=1;i<=m;++i){
read(Q[i].type);Q[i].id=i;
if(Q[i].type==1){
read(Q[i].u);read(Q[i].v);read(Q[i].w);
Q[i].lca=LCA(Q[i].u,Q[i].v);
mx=max(mx,Q[i].w);
}else if(Q[i].type==2){
read(Q[i].u);read(Q[i].w);
mx=max(mx,Q[i].w);
}else if(Q[i].type==3){
read(k);Q[i]=Q[k];Q[i].id=i;Q[i].type=3;
}else read(Q[i].u),read(Q[i].w);
}Solve(1,m,0,mx);
sort(Q+1,Q+m+1,cmpid);
for(int i=1;i<=m;++i){
if(Q[i].type==4){
if(ans[i]==0)ans[i]=-1;
printf("%d\n",ans[i]);
}
}return 0;
}