| 记录编号 |
361091 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[HZOI 2015]榴莲 |
最终得分 |
100 |
| 用户昵称 |
 AntiLeaf |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
1.776 s |
| 提交时间 |
2017-01-03 07:49:40 |
内存使用 |
470.71 MiB |
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define fastcall __attribute__((optimize("-Os")))
#define IL __inline__ __attribute__((always_inline))
using namespace std;
namespace mine{
//#define NEGATE_NEEDED
template<class T>inline void readint(T &__x){
static int __c;
#ifdef NEGATE_NEEDED
static bool __neg;
#endif
__x=0;
#ifdef NEGATE_NEEDED
__neg=false;
#endif
do __c=getchar();while(__c==' '||__c=='\n'||__c=='\r'||__c=='\t');
#ifdef NEGATE_NEEDED
if(__c=='-'){
__neg=true;
__c=getchar();
}
#endif
for(;__c>='0'&&__c<='9';__c=getchar())__x=__x*10+(__c^48);
#ifdef NEGATE_NEEDED
if(__neg)__x=-__x;
#endif
}
template<class T>inline void writeint(T __x){
static int __a[40],__i,__j;
#ifdef NEGATE_NEEDED
static bool __neg;
__neg=__x<0;
if(__neg)__x=-__x;
#endif
__i=0;
do{
__a[__i++]=__x%10^48;
__x/=10;
}while(__x);
#ifdef NEGATE_NEEDED
if(__neg)putchar('-');
#endif
for(__j=__i-1;__j^-1;__j--)putchar(__a[__j]);
}
}
using namespace mine;
const int maxn=100010;
struct A{int u,v,w;A():v(0){}}a[maxn];//v = 0 then modify the subtree
void dfs(int);
int LCA(int,int);
void add(int,int,int,int*);
void getroot(int,int*,int*);
int query(int,int);
void add(int,int,int&);
int sm[maxn*400]={0},lc[maxn*400]={0},rc[maxn*400]={0},cnt=0,add_p,add_d,c1[maxn]={0},c2[maxn]={0},ra[maxn],rb[maxn];
int lgn=0,f[maxn][20],depth[maxn],dfn[maxn],finish[maxn],tim=0;
vector<int>G[maxn];
int n,m,d,x,y,k,cur=0;
int main(){
freopen("Durio_zibethinus_Murr.in","r",stdin);
freopen("Durio_zibethinus_Murr.out","w",stdout);
readint(n);
readint(m);
while((1<<lgn)<n)lgn++;
for(int i=1;i<n;i++){
readint(x);
readint(y);
G[x].push_back(y);
G[y].push_back(x);
}
depth[1]=1;
dfs(1);
for(int j=1;j<=lgn;j++)for(int i=1;i<=n;i++)f[i][j]=f[f[i][j-1]][j-1];
for(int i=1;i<=m;i++){
readint(d);
if(d==1){
readint(x);
readint(y);
readint(k);
int lca=LCA(x,y);
add(dfn[x],k,1,c1);
add(dfn[y],k,1,c1);
add(dfn[lca],k,-1,c1);
if(f[lca][0])add(dfn[f[lca][0]],k,-1,c1);
a[i].u=x;a[i].v=y;a[i].w=k;
}
else if(d==2){
readint(x);
readint(k);
add(dfn[x],k,1,c2);
add(finish[x]+1,k,-1,c2);
a[i].u=x;a[i].w=k;
}
else if(d==3){
readint(k);
x=a[k].u;y=a[k].v;k=a[k].w;
if(y){
int lca=LCA(x,y);
add(dfn[x],k,-1,c1);
add(dfn[y],k,-1,c1);
add(dfn[lca],k,1,c1);
if(f[lca][0])add(dfn[f[lca][0]],k,1,c1);
}
else{
add(dfn[x],k,-1,c2);
add(finish[x]+1,k,1,c2);
a[i].u=x;a[i].w=k;
}
}
else{
readint(x);
readint(k);
ra[0]=rb[0]=0;
getroot(finish[x],c1,ra);
getroot(dfn[x]-1,c1,rb);
getroot(dfn[x],c2,ra);
x=query(0,20000);
if(x)writeint(x);
else{
putchar('-');
putchar('1');
}
putchar('\n');
}
}
return 0;
}
fastcall inline void dfs(int x){
dfn[x]=++tim;
for(int i=0;i<(int)G[x].size();i++)if(G[x][i]!=f[x][0]){
f[G[x][i]][0]=x;
depth[G[x][i]]=depth[x]+1;
dfs(G[x][i]);
}
finish[x]=tim;
}
fastcall IL int LCA(int x,int y){
if(depth[x]<depth[y])swap(x,y);
for(int j=lgn;j>=0;j--)if(depth[f[x][j]]>=depth[y])x=f[x][j];
if(x==y)return x;
for(int j=lgn;j>=0;j--)if(f[x][j]!=f[y][j]){
x=f[x][j];
y=f[y][j];
}
return f[x][0];
}
fastcall IL void add(int x,int y,int d,int *c){
add_p=y;
add_d=d;
while(x<=n){
add(0,20000,c[x]);
x+=x&-x;
}
}
fastcall IL void getroot(int x,int *c,int *a){
while(x){
a[++a[0]]=c[x];
x&=x-1;
}
}
fastcall IL int query(int l,int r){
if(l==r)return l;
int tmp=0;
for(int i=1;i<=ra[0];i++)tmp+=sm[rc[ra[i]]];
for(int i=1;i<=rb[0];i++)tmp-=sm[rc[rb[i]]];
int mid=(l+r)>>1;
if(k<=tmp){
for(int i=1;i<=ra[0];i++)ra[i]=rc[ra[i]];
for(int i=1;i<=rb[0];i++)rb[i]=rc[rb[i]];
return query(mid+1,r);
}
else{
for(int i=1;i<=ra[0];i++)ra[i]=lc[ra[i]];
for(int i=1;i<=rb[0];i++)rb[i]=lc[rb[i]];
k-=tmp;
return query(l,mid);
}
}
fastcall IL void add(int l,int r,int &rt){
if(!rt)rt=++cnt;
sm[rt]+=add_d;
if(l==r)return;
int mid=(l+r)>>1;
if(add_p<=mid)add(l,mid,lc[rt]);
else add(mid+1,r,rc[rt]);
}
/*
10 10
2 1
3 1
4 3
5 4
6 1
7 3
8 3
9 7
10 2
4 1 1
1 3 1 13881
3 2
2 10 12573
2 7 2522
1 10 7 7976
1 7 7 15696
4 2 1
1 3 4 14384
1 10 9 7398
Answer:
-1
7976
*/