2215. [HNOI2016]网络
★★★☆ 输入文件：network_tenderRun.in 输出文件：network_tenderRun.out 简单对比
时间限制：2 s 内存限制：128 MB
【题目描述】
【输入格式】
【输出格式】
【样例输入1】
13 23
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
6 10
6 11
7 12
7 13
2 1
0 8 13 3
0 9 12 5
2 9
2 8
2 2
0 10 12 1
2 2
1 3
2 7
2 1
0 9 5 6
2 4
2 5
1 7
0 9 12 4
0 10 5 7
2 1
2 4
2 12
1 2
2 5
2 3
【样例输出1】
-1
3
5
-1
1
-1
1
1
3
6
7
7
4
6
【提示】
这道题是水题。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int maxn=;
int n,Q,cnt,fir[maxn],nxt[maxn<<],to[maxn<<];
void addedge(int a,int b){
nxt[++cnt]=fir[a];fir[a]=cnt;to[cnt]=b;
} struct Data{
int ID,val;
Data(int id=,int V=){
ID=id;val=V;
}
bool operator <(const Data &a)const{
return val<a.val;
}
}; priority_queue<Data>Mx[maxn<<]; int dep[maxn],fa[maxn],sz[maxn],son[maxn];
bool del[maxn]; void DFS(int x){
sz[x]=;
for(int i=fir[x];i;i=nxt[i])
if(to[i]!=fa[x]){
fa[to[i]]=x;
dep[to[i]]=dep[x]+;
DFS(to[i]);
sz[x]+=sz[to[i]];
if(sz[son[x]]<sz[to[i]])
son[x]=to[i];
}
} int tot,ID[maxn],top[maxn]; void DFS(int x,int tp){
ID[x]=++tot;top[x]=tp;
if(son[x])DFS(son[x],tp);
for(int i=fir[x];i;i=nxt[i])
if(to[i]!=fa[x]&&to[i]!=son[x])
DFS(to[i],to[i]);
} void Build(int x,int l,int r){
Mx[x].push(Data(,-));
if(l==r)return;
int mid=(l+r)>>;
Build(x<<,l,mid);
Build(x<<|,mid+,r);
} int Query(int x,int l,int r,int g){
while(del[Mx[x].top().ID])
Mx[x].pop();
if(l==r)
return Mx[x].top().val;
int mid=(l+r)>>;
if(mid>=g)return max(Mx[x].top().val,Query(x<<,l,mid,g));
else return max(Mx[x].top().val,Query(x<<|,mid+,r,g));
} struct Node{
int l,r;
Node(int L=,int R=){
l=L;r=R;
}
bool operator <(const Node &a)const{
return l<a.l;
}
}st[maxn]; void Update(int x,int l,int r,int a,int b,int id,int val){
if(l>=a&&r<=b){
Mx[x].push(Data(id,val));
return;
}
int mid=(l+r)>>;
if(mid>=a)Update(x<<,l,mid,a,b,id,val);
if(mid<b)Update(x<<|,mid+,r,a,b,id,val);
return;
} void Solve(int x,int y,int id,int val){
int tp=;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])
swap(x,y); st[++tp]=Node(ID[top[x]],ID[x]);
x=fa[top[x]];
} if(dep[x]<dep[y])swap(x,y);
st[++tp]=Node(ID[y],ID[x]); sort(st+,st+tp+); int L=;
for(int i=;i<=tp;i++){
if(L<=st[i].l-)
Update(,,n,L,st[i].l-,id,val);
L=st[i].r+;
} if(L<=n)
Update(,,n,L,n,id,val); return;
} int main(){
#ifndef ONLINE_JUDGE
freopen("network_tenderRun.in","r",stdin);
freopen("network_tenderRun.out","w",stdout);
#endif
scanf("%d%d",&n,&Q);
for(int i=,a,b;i<n;i++){
scanf("%d%d",&a,&b);
addedge(a,b);
addedge(b,a);
} DFS();
DFS(,);
Build(,,n); for(int t=,type,a,b,v;t<=Q;t++){
scanf("%d",&type);
if(type==){
scanf("%d%d%d",&a,&b,&v);
Solve(a,b,t,v);
}
else if(type==){
scanf("%d",&a);
del[a]=true;
}
else if(type==){
scanf("%d",&a);
printf("%d\n",Query(,,n,ID[a]));
}
}
return ;
}
5月20日BZOJ加了一组数据，上面的程序MLE了，只能使用手写栈。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int maxn=;
int n,Q,cnt,fir[maxn],nxt[maxn<<],to[maxn<<];
void addedge(int a,int b){
nxt[++cnt]=fir[a];fir[a]=cnt;to[cnt]=b;
}
priority_queue<int>Mx[maxn<<],del[maxn<<]; int dep[maxn],fa[maxn],sz[maxn],son[maxn],vis[maxn];
int ID[maxn],top[maxn],tot,U[maxn<<],V[maxn<<],val[maxn<<];
int stack[maxn],head; void DFS(int x){
stack[++head]=x;
while(head){
x=stack[head];
if(vis[x]){
if(fa[x]){
sz[fa[x]]+=sz[x];
if(sz[son[fa[x]]]<sz[x])
son[fa[x]]=x;
}
head--;
continue;
}
vis[x]=true;sz[x]=;
for(int i=fir[x];i;i=nxt[i])
if(to[i]!=fa[x]){
fa[to[i]]=x;
dep[to[i]]=dep[x]+;
stack[++head]=to[i];
}
}
} void DFS(int x,int tp){
top[x]=tp;
stack[++head]=x;
while(head){
x=stack[head];
if(vis[x]){
head--;
continue;
}
vis[x]=true;
ID[x]=++tot;
for(int i=fir[x];i;i=nxt[i])
if(to[i]!=fa[x]&&to[i]!=son[x]){
stack[++head]=to[i];
top[to[i]]=to[i];
}
if(son[x]){
stack[++head]=son[x];
top[son[x]]=top[x];
}
}
} int Query(int x,int l,int r,int g){
while(!del[x].empty()&&del[x].top()==Mx[x].top())del[x].pop(),Mx[x].pop();
if(l==r)
return Mx[x].empty()?-:Mx[x].top();
int mid=(l+r)>>,ret=Mx[x].empty()?-:Mx[x].top();
if(mid>=g)return max(ret,Query(x<<,l,mid,g));
else return max(ret,Query(x<<|,mid+,r,g));
} struct Node{
int l,r;
Node(int L=,int R=){
l=L;r=R;
}
bool operator <(const Node &a)const{
return l<a.l;
}
}st[maxn<<]; void Update(int x,int l,int r,int a,int b,int val,int on){
if(l>=a&&r<=b){
if(on)
Mx[x].push(val);
else
del[x].push(val);
return;
}
int mid=(l+r)>>;
if(mid>=a)Update(x<<,l,mid,a,b,val,on);
if(mid<b)Update(x<<|,mid+,r,a,b,val,on);
return;
} void Solve(int x,int y,int val,int on){
int tp=;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])
swap(x,y); st[++tp]=Node(ID[top[x]],ID[x]);
x=fa[top[x]];
} if(dep[x]<dep[y])swap(x,y);
st[++tp]=Node(ID[y],ID[x]); sort(st+,st+tp+); int L=;
for(int i=;i<=tp;i++){
if(L<=st[i].l-)
Update(,,n,L,st[i].l-,val,on);
L=st[i].r+;
} if(L<=n)
Update(,,n,L,n,val,on); return;
} int main(){
#ifndef ONLINE_JUDGE
//freopen("network_tenderRun.in","r",stdin);
//freopen("network_tenderRun.out","w",stdout);
#endif
scanf("%d%d",&n,&Q);
for(int i=,a,b;i<n;i++){
scanf("%d%d",&a,&b);
addedge(a,b);
addedge(b,a);
} DFS();
memset(vis,,sizeof(vis));
DFS(,); for(int t=,type,a;t<=Q;t++){
scanf("%d",&type);
if(type==){
scanf("%d%d%d",&U[t],&V[t],&val[t]);
Solve(U[t],V[t],val[t],);
}
else if(type==){
scanf("%d",&a);
Solve(U[a],V[a],val[a],);
}
else if(type==){
scanf("%d",&a);
printf("%d\n",Query(,,n,ID[a]));
}
}
return ;
}
如下：