| 记录编号 |
261367 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[HNOI 2016] 网络 |
最终得分 |
100 |
| 用户昵称 |
 ZXCVBNM_1 |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
6.013 s |
| 提交时间 |
2016-05-17 11:55:53 |
内存使用 |
30.93 MiB |
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define MAXN 100010
priority_queue<int> q[MAXN*4],qq[MAXN*4];
struct node
{
int left,right;
}cc[MAXN];
struct NODE
{
int left,right;
}tree[MAXN*4];
struct Lovelive
{
int begin,end,next;
}edge[MAXN*2];
int cnt,Head[MAXN],lc,size[MAXN],s1[2*MAXN],s2[2*MAXN],s3[3*MAXN],type[2*MAXN],belong[MAXN],pos[MAXN],P[MAXN][17],deep[MAXN],n,SIZE,V[MAXN];
bool vis[MAXN];
void addedge(int bb,int ee)
{
edge[++cnt].begin=bb;edge[cnt].end=ee;edge[cnt].next=Head[bb];Head[bb]=cnt;
}
void addedge1(int bb,int ee)
{
addedge(bb,ee);addedge(ee,bb);
}
int read()
{
int s=0,fh=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')fh=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=s*10+(ch-'0');ch=getchar();}
return s*fh;
}
void dfs1(int u)
{
int i,v;
vis[u]=true;size[u]=1;
for(i=Head[u];i!=-1;i=edge[i].next)
{
v=edge[i].end;
if(vis[v]==false)
{
deep[v]=deep[u]+1;
P[v][0]=u;
dfs1(v);
size[u]+=size[v];
}
}
}
void Ycl()
{
int i,j;
for(j=1;(1<<j)<=n;j++)
{
for(i=1;i<=n;i++)
{
if(P[i][j-1]!=-1)P[i][j]=P[P[i][j-1]][j-1];
}
}
}
void dfs2(int u,int chain)
{
int k=0,i,v;
pos[u]=++SIZE;belong[u]=chain;V[SIZE]=u;
for(i=Head[u];i!=-1;i=edge[i].next)
{
v=edge[i].end;
if(deep[v]>deep[u]&&size[v]>size[k])k=v;
}
if(k==0)return;
dfs2(k,chain);
for(i=Head[u];i!=-1;i=edge[i].next)
{
v=edge[i].end;
if(deep[v]>deep[u]&&v!=k)dfs2(v,v);
}
}
int LCA(int x,int y)
{
int i,j;
if(deep[x]<deep[y])swap(x,y);
for(i=0;(1<<i)<=deep[x];i++);i--;
for(j=i;j>=0;j--)if(deep[x]-(1<<j)>=deep[y])x=P[x][j];
if(x==y)return x;
for(j=i;j>=0;j--)
{
if(P[x][j]!=-1&&P[x][j]!=P[y][j])
{
x=P[x][j];
y=P[y][j];
}
}
return P[x][0];
}
/*void del(int k,int C)
{
int val;
while(1)
{
val=q[k].top();q[k].pop();
if(val==C)break;
tmp.push(val);
}
while(!tmp.empty()){q[k].push(tmp.top());tmp.pop();}
}*/
int Get_max(int num)
{
while((!qq[num].empty())&&(q[num].top()==qq[num].top())){q[num].pop();qq[num].pop();}
if(q[num].empty())return -1;
return q[num].top();
//if(q[num].empty())printf("-1\n");
//else printf("%d\n",q[num].top());
}
void Build(int k,int l,int r)
{
tree[k].left=l;tree[k].right=r;
if(l==r)return;
int mid=(l+r)/2;
Build(k*2,l,mid);Build(k*2+1,mid+1,r);
}
void Change(int k,int l,int r,int C,int zs)
{
if(l<=tree[k].left&&tree[k].right<=r)
{
if(zs==1)q[k].push(C);
else qq[k].push(C);//del(V[tree[k].left],C);
return;
}
int mid=(tree[k].left+tree[k].right)/2;
if(r<=mid)Change(k*2,l,r,C,zs);
else if(l>mid)Change(k*2+1,l,r,C,zs);
else {Change(k*2,l,mid,C,zs);Change(k*2+1,mid+1,r,C,zs);}
}
int Query(int k,int lr)
{
if(tree[k].left==tree[k].right)return Get_max(k);
int mid=(tree[k].left+tree[k].right)/2;
if(lr<=mid)return max(Get_max(k),Query(k*2,lr));
else return max(Get_max(k),Query(k*2+1,lr));
}
void Solve_get(int x,int fa)
{
while(belong[x]!=belong[fa])
{
//Get(1,pos[belong[x]],pos[x]);
cc[++lc].left=pos[belong[x]];cc[lc].right=pos[x];
x=P[belong[x]][0];
}
if(x!=fa){cc[++lc].left=pos[fa];cc[lc].right=pos[x];}//Get(1,pos[fa],pos[x]);
}
bool cmp(node aa,node bb){return aa.left<bb.left;}
int main()
{
freopen("network_tenderRun.in","r",stdin);
freopen("network_tenderRun.out","w",stdout);
int m,i,bb,ee,lca,S1,S2,S3,num,j;
n=read();m=read();
memset(Head,-1,sizeof(Head));cnt=1;
for(i=1;i<n;i++)
{
bb=read();ee=read();
addedge1(bb,ee);
}
dfs1(1);Ycl();
dfs2(1,1);
Build(1,1,n);
for(i=1;i<=m;i++)
{
type[i]=read();
if(type[i]==0)
{
s1[i]=read();s2[i]=read();s3[i]=read();
lca=LCA(s1[i],s2[i]);
lc=0;
if(lca!=s1[i]&&lca!=s2[i])
{
Solve_get(s1[i],lca);
Solve_get(s2[i],lca);
}
else if(lca==s1[i])Solve_get(s2[i],lca);
else Solve_get(s1[i],lca);
cc[++lc].left=0;cc[lc].right=0;cc[++lc].left=n+1;cc[lc].right=n+1;
sort(cc+1,cc+lc+1,cmp);
for(j=1;j<=lc;j++)if((cc[j].right+1)<=(cc[j+1].left-1))Change(1,cc[j].right+1,cc[j+1].left-1,s3[i],1);
}
else if(type[i]==1)
{
num=read();
S1=s1[num];S2=s2[num];S3=s3[num];
lca=LCA(S1,S2);
lc=0;
if(lca!=S1&&lca!=S2)
{
Solve_get(S1,lca);
Solve_get(S2,lca);
}
else if(lca==S1)Solve_get(S2,lca);
else Solve_get(S1,lca);
cc[++lc].left=0;cc[lc].right=0;cc[++lc].left=n+1;cc[lc].right=n+1;
sort(cc+1,cc+lc+1,cmp);
for(j=1;j<=lc;j++)if((cc[j].right+1)<=(cc[j+1].left-1))Change(1,cc[j].right+1,cc[j+1].left-1,S3,-1);
}
else
{
num=read();
printf("%d\n",Query(1,pos[num]));
/*while((!qq[num].empty())&&(q[num].top()==qq[num].top())){q[num].pop();qq[num].pop();}
if(q[num].empty())printf("-1\n");
else printf("%d\n",q[num].top());*/
}
}
fclose(stdin);
fclose(stdout);
return 0;
}