NC20393. [SDOI2017]树点涂色
描述
输入描述
第一行两个数n,m。
接下来n-1行，每行两个数a,b，表示a与b之间有一条边。
接下来m行，表示操作，格式见题目描述1≤ n,m≤100000
输出描述
每当出现2,3操作，输出一行。
如果是2操作，输出一个数表示路径的权值
如果是3操作，输出一个数表示权值的最大值
示例1
输入:
5 6 1 2 2 3 3 4 3 5 2 4 5 3 3 1 4 2 4 5 1 5 2 4 5
输出:
3 4 2 2
C++14(g++5.4) 解法, 执行用时: 343ms, 内存消耗: 24804K, 提交时间: 2020-04-03 17:53:06
#include<bits/stdc++.h>
#define Lson k<<1,l,mid
#define Rson k<<1|1,mid+1,r
#define lson o[x].son[0]
#define rson o[x].son[1]
using namespace std;
const int MX=4e5+9;
int n,m;
vector<int> vec[MX];
int siz[MX],fa[MX],son[MX],dis[MX];
void dfs1(int u,int f,int di){
dis[u]=di,fa[u]=f,son[u]=0,siz[u]=1;
for( int i=0 ; i<vec[u].size() ; i++ ){
int v=vec[u][i];
if( v!=f ){
dfs1(v,u,di+1);
siz[u]+=siz[v];
if( son[u]==0 || siz[son[u]]<siz[v] )
son[u]=v;
}
}
}
int st[MX],ed[MX],pos[MX],top[MX],tot=0;
void dfs2(int u,int tp){
top[u]=tp;
st[u]=++tot;
pos[tot]=u;
if( son[u] )
dfs2(son[u],tp);
for( int i=0 ; i<vec[u].size() ; i++ ){
int v=vec[u][i];
if( !st[v] )
dfs2(v,v);
}
ed[u]=tot;
}
int t[MX],laze[MX];
void build(int k,int l,int r){
laze[k]=0;
if( l==r ){
t[k]=dis[pos[l]];
return ;
}
int mid=(l+r)>>1;
build(Lson);
build(Rson);
t[k]=max(t[k<<1],t[k<<1|1]);
}
void pushdown(int k){
if( laze[k]!=0 ){
laze[k<<1]+=laze[k];
laze[k<<1|1]+=laze[k];
t[k<<1]+=laze[k];
t[k<<1|1]+=laze[k];
laze[k]=0;
}
}
void update(int k,int l,int r,int L,int R,int val){
if( L<=l && r<=R ){
t[k]+=val;
laze[k]+=val;
return ;
}
int mid=(l+r)>>1;
pushdown(k);
if( L<=mid )
update(Lson,L,R,val);
if( mid<R )
update(Rson,L,R,val);
t[k]=max(t[k<<1],t[k<<1|1]);
}
int que(int k,int l,int r,int L,int R){
if( L<=l && r<=R )
return t[k];
pushdown(k);
int mid=(l+r)>>1,ans=0;
if( L<=mid )
ans=max(ans,que(Lson,L,R));
if( mid<R )
ans=max(ans,que(Rson,L,R));
return ans;
}
int lca(int u,int v){
while( top[u]!=top[v] ){
if( dis[top[u]]<dis[top[v]] )
swap(u,v);
u=fa[top[u]];
}
return dis[u]<dis[v]?u:v;
}
struct node{
int fa;
int son[2];
}o[MX*20];
int isroot(int x){
return o[o[x].fa].son[1]!=x&&o[o[x].fa].son[0]!=x;
}
int get(int x){
return o[o[x].fa].son[1]==x;
}
void rotate(int x){
int f=o[x].fa,ff=o[f].fa,kx=get(x),kf=get(f);
o[x].fa=ff;
if( !isroot(f) )
o[ff].son[kf]=x;
o[f].son[kx]=o[x].son[!kx],o[o[x].son[!kx]].fa=f;
o[x].son[!kx]=f,o[f].fa=x;
}
void splay(int x){
while( !isroot(x) ){
int f=o[x].fa;
if( !isroot(o[x].fa) ){
if( get(x)==get(f) )
rotate(f);
else
rotate(x);
}
rotate(x);
}
}
int fin_rt(int x){
while( lson )
x=lson;
return x;
}
void access(int x){
for( int y=0,z ; x ; y=x,x=o[x].fa){
splay(x);
if( rson ){
z=fin_rt(rson);
update(1,1,n,st[z],ed[z],1);
}
rson=y;
if( y ){
z=fin_rt(y);
update(1,1,n,st[z],ed[z],-1);
}
}
}
int main()
{
//freopen("input.txt","r",stdin);
scanf("%d %d",&n,&m);
for( int i=1,u,v ; i<n ; i++ ){
scanf("%d %d",&u,&v);
vec[u].push_back(v);
vec[v].push_back(u);
}
dfs1(1,0,1);
dfs2(1,1);
build(1,1,n);
for( int i=1 ; i<=n ; i++ )
o[i].fa=fa[i];
int order,x,y;
while( m-- ){
scanf("%d",&order);
if( order==1 ){
scanf("%d",&x);
access(x);
}
else if( order==2 ){
scanf("%d %d",&x,&y);
int lc=lca(x,y);
printf("%d\n",que(1,1,n,st[x],st[x])+que(1,1,n,st[y],st[y])-2*que(1,1,n,st[lc],st[lc])+1);
}
else{
scanf("%d",&x);
printf("%d\n",que(1,1,n,st[x],ed[x]));
}
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 482ms, 内存消耗: 21348K, 提交时间: 2019-04-05 17:35:15
#include<bits/stdc++.h>
#define lc ch[u][0]
#define rc ch[u][1]
using namespace std;
const int N=100010;
int n,m,idx,now;
int cnt=0,hed[N],to[N+N],nxt[N+N];
int lb[N*4],rb[N*4],md[N*4],mm[N*4],lz[N*4];
int ch[N][2],f[N],v[N],lx[N],rx[N],sum[N],mx[N];
int dfn[N],rev[N],d[N],low[N],st[N][20];
inline int Max(int x,int y) { return x>y? x:y; }
inline void add(int x,int y) { to[++cnt]=y,nxt[cnt]=hed[x],hed[x]=cnt; }
void dfs(int u,int ff) {
d[now=rev[dfn[u]=++idx]=u]=d[st[u][0]=f[u]=ff]+1;
for(int i=1;i<20;i++) st[u][i]=st[st[u][i-1]][i-1];
for(int i=hed[u];i;i=nxt[i]) if(ff!=to[i]) dfs(to[i],u);
low[u]=now;
}
int LCA(int x,int y) {
if(d[x]<d[y]) swap(x,y);
for(int i=19;i>=0;i--) if(d[st[x][i]]>=d[y]) x=st[x][i];
if(x==y) return x;
for(int i=19;i>=0;i--) if(st[x][i]!=st[y][i]) x=st[x][i],y=st[y][i];
return st[x][0];
}
void pushup(int u) { md[u]=Max(md[u*2],md[u*2+1]); }
void build(int u,int l,int r) {
lb[u]=l,rb[u]=r,mm[u]=(l+r)>>1; if(l>=r) { md[u]=d[rev[l]];return ; }
build(u*2,l,mm[u]),build(u*2+1,mm[u]+1,r),pushup(u);
}
void mdy(int u,int l,int r,int w);
void pushdown(int u) {
if(lz[u])
mdy(u*2,lb[u],mm[u],lz[u]),mdy(u*2+1,mm[u]+1,rb[u],lz[u]),lz[u]=0;
}
void mdy(int u,int l,int r,int w) {
if(lb[u]==l&&rb[u]==r) { md[u]+=w;lz[u]+=w;return; }
pushdown(u);
if(r<=mm[u]) mdy(u*2,l,r,w); else if(l>mm[u]) mdy(u*2+1,l,r,w);
else mdy(u*2,l,mm[u],w),mdy(u*2+1,mm[u]+1,r,w);
pushup(u);
}
int ask(int u,int l,int r) {
if(lb[u]==l&&rb[u]==r) return md[u];
pushdown(u);
if(r<=mm[u]) return ask(u*2,l,r); if(l>mm[u]) return ask(u*2+1,l,r);
return Max(ask(u*2,l,mm[u]),ask(u*2+1,mm[u]+1,r));
}
inline bool nroot(int u) { return ch[f[u]][0]==u||ch[f[u]][1]==u; }
inline void rotate(int u) {
int y=f[u],z=f[y],k=ch[y][1]==u,w=ch[u][k^1];
if(nroot(y)) ch[z][ch[z][1]==y]=u; ch[u][k^1]=y,ch[y][k]=w;
if(w) f[w]=y; f[y]=u,f[u]=z;
}
inline void splay(int u) {
int y=u;
for(;nroot(u);rotate(u))
if(nroot(f[u]))
rotate((ch[f[u]][0]==u)^(ch[f[f[u]]][0]==f[u])? u:f[u]);
}
inline int findroot(int u) { while(lc) u=lc; return u; }
inline void access(int u) {
for(int y=0,x;u;u=f[y=u]) {
splay(u);
if(rc) x=findroot(rc),mdy(1,dfn[x],dfn[low[x]],1);
rc=y;
if(rc) x=findroot(rc),mdy(1,dfn[x],dfn[low[x]],-1);
}
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),add(x,y),add(y,x);
dfs(1,0),build(1,1,n);
while(m--) {
int opt,x,y,lca;scanf("%d%d",&opt,&x);
if(opt==1) access(x);
else if(opt==2) {
scanf("%d",&y),lca=LCA(x,y);
printf("%d\n",ask(1,dfn[x],dfn[x])+ask(1,dfn[y],dfn[y])
-ask(1,dfn[lca],dfn[lca])*2+1);
}
else printf("%d\n",ask(1,dfn[x],dfn[low[x]]));
}
return 0;
}