树链剖分

  1. 1 【bzoj 1036】[ZJOI2008]树的统计Count
  2. 2 【bzoj 4034】[HAOI2015]T2
  3. 3 【bzoj 4196】[Noi2015]软件包管理器
  4. 4 树的查询(qtree)
  5. 5 种草地(grassplant)
  6. 6 查询树(tree)

树链剖分详解

1 【bzoj 1036】[ZJOI2008]树的统计Count

权值在点上,单点修改,询问路径上的MAX和SUM

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
const int N=30001;
char s[10];
int n,x,y,totw,tot=1,Q,ans,f1,f2;
int a[N],fa[N],dep[N],size[N],son[N],top[N],w[N];
vector<int> to[N];
struct node{
int l,r,ls,rs,maxx,sum;
}t[N*2];
void dfs1(int x)
{
size[x]++;
for(int i=0;i<to[x].size();i++)
{
int y=to[x][i];
if(fa[x]==y) continue;
fa[y]=x;dep[y]=dep[x]+1;
dfs1(y);size[x]+=size[y];
if(size[son[x]]<size[y]) son[x]=y;
}
}
void dfs2(int x)
{
int y=son[x];if(!y) return;
top[y]=top[x];w[y]=++totw;dfs2(y);
for(int i=0;i<to[x].size();i++)
{
y=to[x][i];
if(fa[x]==y||son[x]==y) continue;
top[y]=y;w[y]=++totw;dfs2(y);
}
}
void Build(int root,int L,int R)
{
t[root].l=L;t[root].r=R;
if(L==R)
{
t[root].sum=t[root].maxx=a[L];return;
}
int mid=(L+R)>>1;
t[root].ls=++tot;Build(t[root].ls,L,mid);
t[root].rs=++tot;Build(t[root].rs,mid+1,R);
t[root].sum=t[t[root].ls].sum+t[t[root].rs].sum;
t[root].maxx=max(t[t[root].ls].maxx,t[t[root].rs].maxx);
}
void Change(int root,int num,int d)
{
if(t[root].l==t[root].r)
{
t[root].sum=t[root].maxx=d;return;
}
int mid=(t[root].l+t[root].r)>>1;
if(num<=mid) Change(t[root].ls,num,d);
else Change(t[root].rs,num,d);
t[root].sum=t[t[root].ls].sum+t[t[root].rs].sum;
t[root].maxx=max(t[t[root].ls].maxx,t[t[root].rs].maxx);
}
int Sum(int root,int L,int R)
{
if(L<=t[root].l&&t[root].r<=R) return t[root].sum;
int mid=(t[root].l+t[root].r)>>1,z=0;
if(L<=mid) z+=Sum(t[root].ls,L,R);
if(R>mid) z+=Sum(t[root].rs,L,R);
return z;
}
int Max(int root,int L,int R)
{
if(L<=t[root].l&&t[root].r<=R) return t[root].maxx;
int mid=(t[root].l+t[root].r)>>1,z=-30000;
if(L<=mid) z=max(z,Max(t[root].ls,L,R));
if(R>mid) z=max(z,Max(t[root].rs,L,R));
return z;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
to[x].push_back(y);to[y].push_back(x);
}
dep[1]=1;dfs1(1);
top[1]=1;w[1]=++totw;dfs2(1);
for(int i=1;i<=n;i++) scanf("%d",&a[w[i]]);
Build(1,1,n);
scanf("%d",&Q);
while(Q--)
{
scanf("%s%d%d",s,&x,&y);
if(s[0]=='C') Change(1,w[x],y);
else if(s[1]=='M')
{
ans=-30000;
while(1)
{
f1=top[x];f2=top[y];
if(f1==f2)
{
if(w[x]<w[y]) ans=max(ans,Max(1,w[x],w[y]));
else ans=max(ans,Max(1,w[y],w[x]));
break;
}
else
{
if(dep[f1]<dep[f2]) swap(x,y),swap(f1,f2);
ans=max(ans,Max(1,w[f1],w[x]));
x=fa[f1];
}
}
printf("%d\n",ans);
}
else
{
ans=0;
while(1)
{
f1=top[x];f2=top[y];
if(f1==f2)
{
if(w[x]<w[y]) ans+=Sum(1,w[x],w[y]);
else ans+=Sum(1,w[y],w[x]);
break;
}
else
{
if(dep[f1]<dep[f2]) swap(x,y),swap(f1,f2);
ans+=Sum(1,w[f1],w[x]);
x=fa[f1];
}
}
printf("%d\n",ans);
}
}
}

2 【bzoj 4034】[HAOI2015]T2

操作 1 :把某个节点 x 的点权增加 a 。
操作 2 :把某个节点 x 为根的子树中所有点的点权都增加 a 。
操作 3 :询问某个节点 x 到根的路径中所有点的点权和。

第二次dfs的时候求dfs序,按st[]建树,操作二就是修改st[]到ed[]

#include<cstdio>
#include<vector>
using namespace std;
const int N=100001;
int n,m,tot,totw,x,y,k,f1;
long long ans;
int size[N],fa[N],dep[N],st[N],ed[N],son[N],top[N],a[N],b[N];
vector<int> to[N];
struct node{
int l,r,ls,rs;long long mark,sum;
}t[N*2];
void dfs1(int x)
{
size[x]=1;
for(int i=0;i<to[x].size();i++)
{
int y=to[x][i];
if(fa[x]==y) continue;
dep[y]=dep[x]+1;fa[y]=x;
dfs1(y);size[x]+=size[y];
if(size[son[x]]<size[y]) son[x]=y;
}
}
void dfs2(int x)
{
st[x]=ed[x]=++totw;
if(!son[x]) return;
int y=son[x];top[y]=top[x];dfs2(y);
for(int i=0;i<to[x].size();i++)
{
y=to[x][i];
if(y==fa[x]||y==son[x]) continue;
top[y]=y;dfs2(y);
}
ed[x]=totw;
}
void push_down(int root)
{
int L=t[root].ls,R=t[root].rs;
if(!L&&!R) return;
long long ma=t[root].mark;t[root].mark=0;
t[L].mark+=ma;t[L].sum+=ma*(t[L].r-t[L].l+1);
t[R].mark+=ma;t[R].sum+=ma*(t[R].r-t[R].l+1);
}
void Build(int root,int L,int R)
{
t[root].l=L;t[root].r=R;
if(L==R)
{
t[root].sum=b[L];return;
}
int mid=(L+R)>>1;
t[root].ls=++tot;Build(t[root].ls,L,mid);
t[root].rs=++tot;Build(t[root].rs,mid+1,R);
t[root].sum=t[t[root].ls].sum+t[t[root].rs].sum;
}
void add(int root,int L,int R,int d)
{
if(t[root].mark) push_down(root);
if(L<=t[root].l&&R>=t[root].r)
{
t[root].mark+=(long long)d;t[root].sum+=(long long)(t[root].r-t[root].l+1)*d;
return;
}
int mid=(t[root].l+t[root].r)>>1;
if(L<=mid) add(t[root].ls,L,R,d);
if(R>mid) add(t[root].rs,L,R,d);
t[root].sum=t[t[root].ls].sum+t[t[root].rs].sum;
}
long long Sum(int root,int L,int R)
{
if(t[root].mark) push_down(root);
if(L<=t[root].l&&t[root].r<=R) return t[root].sum;
int mid=(t[root].l+t[root].r)>>1;long long sum=0;
if(L<=mid) sum+=Sum(t[root].ls,L,R);
if(R>mid) sum+=Sum(t[root].rs,L,R);
return sum;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
to[x].push_back(y);to[y].push_back(x);
}
dep[1]=1;top[1]=1;
dfs1(1);dfs2(1);
for(int i=1;i<=n;i++) b[st[i]]=a[i];
tot=1;Build(1,1,n);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&k,&x);
if(k==1)
{
scanf("%d",&y);
add(1,st[x],st[x],y);
}
else if(k==2)
{
scanf("%d",&y);
add(1,st[x],ed[x],y);
}
else
{
ans=0;f1=top[x];
while(f1!=1)
{
ans+=Sum(1,st[f1],st[x]);
x=fa[f1];f1=top[x];
}
ans+=Sum(1,1,st[x]);
printf("%lld\n",ans);
}
}
}

3 【bzoj 4196】[Noi2015]软件包管理器

install 向上求sum,并都改成1
uninstall 向下求sum,并都改成0

不要吐槽我把sum和change写一块儿了

#include<cstring>
#include<cstdio>
using namespace std;
const int N=100001;
int n,m,tot,x,ans,f;
int size[N],dep[N],fa[N],son[N],top[N],fi[N],ed[N];
int st[N],next[N],to[N];
char s[10];
struct node{
int l,r,ls,rs,mark,sum;
}t[N*2];
void dfs1(int x)
{
size[x]=1;dep[x]=dep[fa[x]]+1;
for(int i=st[x];i;i=next[i])
{
int y=to[i];
dfs1(y);size[x]+=size[y];
if(son[x]==-1||(son[x]!=-1&&size[y]>size[son[x]])) son[x]=y;
}
}
void dfs2(int x)
{
fi[x]=ed[x]=++tot;
if(son[x]==-1) return;
int y=son[x];
top[y]=top[x];dfs2(y);
for(int i=st[x];i;i=next[i])
{
y=to[i];
if(y==son[x]) continue;
top[y]=y;dfs2(y);
}
ed[x]=tot;
}
void Build(int root,int L,int R)
{
t[root].l=L;t[root].r=R;
if(L==R) return;
int mid=(L+R)>>1;
t[root].ls=++tot; Build(tot,L,mid);
t[root].rs=++tot; Build(tot,mid+1,R);
}
void push_down(int root)
{
int ma=t[root].mark,L=t[root].ls,R=t[root].rs;
t[L].mark=ma;t[L].sum=(t[L].r-t[L].l+1)*ma;
t[R].mark=ma;t[R].sum=(t[R].r-t[R].l+1)*ma;
}
int Change(int root,int L,int R,int d)
{
if(L>R) return 0;
if(L<=t[root].l&&R>=t[root].r)
{
int y=t[root].sum;
t[root].sum=d*(t[root].r-t[root].l+1);
t[root].mark=d;return y;
}
if(t[root].mark!=-1) push_down(root);
int mid=(t[root].l+t[root].r)>>1,sum=0;
if(L<=mid) sum+=Change(t[root].ls,L,R,d);
if(R>mid) sum+=Change(t[root].rs,L,R,d);
t[root].sum=t[t[root].ls].sum+t[t[root].rs].sum;
if(t[t[root].ls].mark==t[t[root].rs].mark) t[root].mark=t[t[root].ls].mark;
else t[root].mark=-1;
return sum;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
scanf("%d",&x);fa[i]=x;
next[++tot]=st[x];st[x]=tot;to[tot]=i;
}
memset(son,-1,sizeof(son));
tot=0;dfs1(0);dfs2(0);
tot=1;Build(1,1,n);
scanf("%d",&m);
while(m--)
{
scanf("%s%d",s,&x);
if(s[0]=='i')
{
ans=dep[x];f=top[x];
while(f)
{
ans-=Change(1,fi[f],fi[x],1);
x=fa[f];f=top[x];
}
ans-=Change(1,1,fi[x],1);
printf("%d\n",ans);
}
else printf("%d\n",Change(1,fi[x],ed[x],0));
}
}

好吧分开写是这样的,其实没啥区别了

int Sum(int root,int L,int R)
{
if(L>R) return 0;
if(L<=t[root].l&&R>=t[root].r) return t[root].sum;
if(t[root].mark!=-1) push_down(root);
int mid=(t[root].l+t[root].r)>>1,sum=0;
if(L<=mid) sum+=Sum(t[root].ls,L,R);
if(R>mid) sum+=Sum(t[root].rs,L,R);
return sum;
}
void Change(int root,int L,int R,int d)
{
if(L>R) return;
if(L<=t[root].l&&R>=t[root].r)
{
t[root].sum=d*(t[root].r-t[root].l+1);
t[root].mark=d;return;
}
if(t[root].mark!=-1) push_down(root);
int mid=(t[root].l+t[root].r)>>1;
if(L<=mid) Change(t[root].ls,L,R,d);
if(R>mid) Change(t[root].rs,L,R,d);
t[root].sum=t[t[root].ls].sum+t[t[root].rs].sum;
if(t[t[root].ls].mark==t[t[root].rs].mark) t[root].mark=t[t[root].ls].mark;
else t[root].mark=-1;
}

4 树的查询(qtree)

#include<iostream>
#include<cstdio>
using namespace std;
const int N=10005;
int n,x,y,z,tot,ans,f1,f2;
int siz[N],dep[N],top[N],fa[N],son[N],w[N],a[N];
int next[N*2],st[N*2],to[N*2];
char s[10];
struct gggg{
int x,y,z;
}g[N];
struct node{
int l,r,ls,rs,maxx;
}t[N*2];
void dfs1(int x)
{
siz[x]=1;dep[x]=dep[fa[x]]+1;
for(int i=st[x];i;i=next[i])
{
int y=to[i];
if(fa[x]==y) continue;
fa[y]=x;dfs1(y);siz[x]+=siz[y];
if(siz[y]>siz[son[x]]) son[x]=y;
}
}
void dfs2(int x)
{
w[x]=++tot;
if(!son[x]) return;
int y=son[x];top[y]=top[x];dfs2(y);
for(int i=st[x];i;i=next[i])
{
y=to[i];
if(fa[x]==y||son[x]==y) continue;
top[y]=y;dfs2(y);
}
}
void Build(int root,int L,int R)
{
t[root].l=L;t[root].r=R;
if(L==R)
{
t[root].maxx=a[L];return;
}
int mid=(L+R)>>1;
t[root].ls=++tot;Build(tot,L,mid);
t[root].rs=++tot;Build(tot,mid+1,R);
t[root].maxx=max(t[t[root].ls].maxx,t[t[root].rs].maxx);
}
void change(int root,int pos,int d)
{
if(t[root].l==t[root].r)
{
t[root].maxx=d;return;
}
int mid=(t[root].l+t[root].r)>>1;
if(pos<=mid) change(t[root].ls,pos,d);
else change(t[root].rs,pos,d);
t[root].maxx=max(t[t[root].ls].maxx,t[t[root].rs].maxx);
}
int Max(int root,int L,int R)
{
if(L<=t[root].l&&R>=t[root].r) return t[root].maxx;
int mid=(t[root].l+t[root].r)>>1,maxx=-2147483647;
if(L<=mid) maxx=Max(t[root].ls,L,R);
if(R>mid) maxx=max(maxx,Max(t[root].rs,L,R));
return maxx;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
scanf("%d%d%d",&g[i].x,&g[i].y,&g[i].z);
next[++tot]=st[g[i].x];st[g[i].x]=tot;to[tot]=g[i].y;
next[++tot]=st[g[i].y];st[g[i].y]=tot;to[tot]=g[i].x;
}
tot=0;dfs1(1);top[1]=1;dfs2(1);
for(int i=1;i<n;i++)
{
if(dep[g[i].x]<dep[g[i].y]) swap(g[i].x,g[i].y);
a[w[g[i].x]]=g[i].z;
}
tot=1;Build(1,1,n);
while(scanf("%s",s)&&s[0]!='D')
{
scanf("%d%d",&x,&y);
if(s[0]=='C') change(1,w[g[x].x],y);
else
{
ans=-2147483647;
f1=top[x];f2=top[y];
while(f1!=f2)
{
if(dep[f1]<dep[f2]) swap(x,y),swap(f1,f2);
ans=max(ans,Max(1,w[f1],w[x]));
x=fa[x];f1=top[x];f2=top[y];
}
if(w[x]>w[y]) swap(x,y);
ans=max(ans,Max(1,w[x]+1,w[y]));
printf("%d\n",ans);
}
}
}

5 种草地(grassplant)

#include<iostream>
#include<cstdio>
using namespace std;
const int N=100001;
int n,m,tot,ans,x,y,f1,f2;
int size[N],dep[N],fa[N],son[N],w[N],top[N];
int st[N*2],next[N*2],to[N*2];
char s[5];
struct node{
int l,r,ls,rs,sum,mark;
}t[N*2];
void dfs1(int x)
{
size[x]=1;dep[x]=dep[fa[x]]+1;
for(int i=st[x];i;i=next[i])
{
int y=to[i];
if(fa[x]==y) continue;
fa[y]=x;dfs1(y);size[x]+=size[y];
if(size[y]>size[son[x]]) son[x]=y;
}
}
void dfs2(int x)
{
w[x]=++tot;
if(!son[x]) return;
int y=son[x];top[y]=top[x];dfs2(y);
for(int i=st[x];i;i=next[i])
{
y=to[i];
if(fa[x]==y||son[x]==y) continue;
top[y]=y;dfs2(y);
}
}
void Build(int root,int L,int R)
{
t[root].l=L;t[root].r=R;
if(L==R) return;
int mid=(L+R)>>1;
t[root].ls=++tot; Build(tot,L,mid);
t[root].rs=++tot; Build(tot,mid+1,R);
}
void push_down(int root)
{
int L=t[root].ls,R=t[root].rs,ma=t[root].mark;t[root].mark=0;
t[L].mark+=ma;t[L].sum+=(t[L].r-t[L].l+1)*ma;
t[R].mark+=ma;t[R].sum+=(t[R].r-t[R].l+1)*ma;
}
void Add(int root,int L,int R)
{
if(L<=t[root].l&&t[root].r<=R)
{
t[root].mark++;
t[root].sum+=t[root].r-t[root].l+1;
return;
}
if(t[root].mark) push_down(root);
int mid=(t[root].l+t[root].r)>>1;
if(L<=mid) Add(t[root].ls,L,R);
if(R>mid) Add(t[root].rs,L,R);
}
int Sum(int root,int L,int R)
{
if(L<=t[root].l&&t[root].r<=R) return t[root].sum;
if(t[root].mark) push_down(root);
int mid=(t[root].l+t[root].r)>>1,sum=0;
if(L<=mid) sum+=Sum(t[root].ls,L,R);
if(R>mid) sum+=Sum(t[root].rs,L,R);
return sum;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
next[++tot]=st[x];st[x]=tot;to[tot]=y;
next[++tot]=st[y];st[y]=tot;to[tot]=x;
}
tot=0;dfs1(1);top[1]=1;dfs2(1);
tot=1;Build(1,1,n);
while(m--)
{
scanf("%s%d%d",s,&x,&y);
if(s[0]=='P')
{
f1=top[x];f2=top[y];
while(f1!=f2)
{
if(dep[f1]<dep[f2]) swap(x,y),swap(f1,f2);
Add(1,w[f1],w[x]);x=fa[f1];
f1=top[x];f2=top[y];
}
if(dep[x]>dep[y]) swap(x,y);
Add(1,w[x]+1,w[y]);
}
else
{
ans=0;
f1=top[x];f2=top[y];
while(f1!=f2)
{
if(dep[f1]<dep[f2]) swap(x,y),swap(f1,f2);
ans+=Sum(1,w[f1],w[x]);x=fa[f1];
f1=top[x];f2=top[y];
}
if(dep[x]>dep[y]) swap(x,y);
ans+=Sum(1,w[x]+1,w[y]);
printf("%d\n",ans);
}
}
}

6 查询树(tree)

#include<iostream>
#include<cstdio>
using namespace std;
const int N=10001;
int n,tot,x,y,z,f1,f2,ans;
int size[N],dep[N],fa[N],son[N],w[N],top[N],val[N];
int next[N*2],st[N*2],to[N*2];
char s[5];
struct node{
int x,y,z;
}a[N];
struct tree{
int l,r,ls,rs,maxx,minn,mark;
}t[N*2];
void dfs1(int x)
{
size[x]=1;dep[x]=dep[fa[x]]+1;
for(int i=st[x];i;i=next[i])
{
int y=to[i];
if(fa[x]==y) continue;
fa[y]=x;dfs1(y);size[x]+=size[y];
if(size[y]>size[son[x]]) son[x]=y;
}
}
void dfs2(int x)
{
w[x]=++tot;
if(!son[x]) return;
int y=son[x];top[y]=top[x];dfs2(y);
for(int i=st[x];i;i=next[i])
{
y=to[i];
if(fa[x]==y||son[x]==y) continue;
top[y]=y;dfs2(y);
}
}
void Build(int root,int L,int R)
{
t[root].l=L;t[root].r=R;
if(L==R)
{
t[root].maxx=t[root].minn=val[L];return;
}
int mid=(L+R)>>1;
t[root].ls=++tot;Build(tot,L,mid);
t[root].rs=++tot;Build(tot,mid+1,R);
t[root].maxx=max(t[t[root].ls].maxx,t[t[root].rs].maxx);
t[root].minn=min(t[t[root].ls].minn,t[t[root].rs].minn);
}
void push_down(int root)
{
int L=t[root].ls,R=t[root].rs,x,y;
t[root].mark=0;
x=t[L].maxx;y=t[L].minn;t[L].maxx=-y;t[L].minn=-x;t[L].mark=1-t[L].mark;
x=t[R].maxx;y=t[R].minn;t[R].maxx=-y;t[R].minn=-x;t[R].mark=1-t[R].mark;
}
void Change(int root,int pos,int val)
{
if(t[root].l==t[root].r)
{
t[root].maxx=t[root].minn=val;return;
}
if(t[root].mark) push_down(root);
int mid=(t[root].l+t[root].r)>>1;
if(pos<=mid) Change(t[root].ls,pos,val);
else Change(t[root].rs,pos,val);
t[root].maxx=max(t[t[root].ls].maxx,t[t[root].rs].maxx);
t[root].minn=min(t[t[root].ls].minn,t[t[root].rs].minn);
}
void Fan(int root,int L,int R)
{
if(L<=t[root].l&&R>=t[root].r)
{
t[root].mark=1-t[root].mark;
int x=t[root].maxx,y=t[root].minn;
t[root].maxx=-y;t[root].minn=-x;
return;
}
if(t[root].mark) push_down(root);
int mid=(t[root].l+t[root].r)>>1;
if(L<=mid) Fan(t[root].ls,L,R);
if(R>mid) Fan(t[root].rs,L,R);
t[root].maxx=max(t[t[root].ls].maxx,t[t[root].rs].maxx);
t[root].minn=min(t[t[root].ls].minn,t[t[root].rs].minn);
}
int Max(int root,int L,int R)
{
if(L<=t[root].l&&R>=t[root].r) return t[root].maxx;
if(t[root].mark) push_down(root);
int mid=(t[root].l+t[root].r)>>1,maxx=-2147483647;
if(L<=mid) maxx=Max(t[root].ls,L,R);
if(R>mid) maxx=max(maxx,Max(t[root].rs,L,R));
return maxx;
}
int main()
{
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<n;i++)
{
scanf("%d%d%d",&x,&y,&z);a[i].x=x;a[i].y=y;a[i].z=z;
next[++tot]=st[x];st[x]=tot;to[tot]=y;
next[++tot]=st[y];st[y]=tot;to[tot]=x;
}
tot=0;top[1]=1;dfs1(1);dfs2(1);
for(int i=1;i<n;i++)
{
if(dep[a[i].x]<dep[a[i].y]) swap(a[i].x,a[i].y);
val[w[a[i].x]]=a[i].z;
}
tot=1;Build(1,1,n);
while(scanf("%s",s)&&s[0]!='D')
{
scanf("%d%d",&x,&y);
if(s[0]=='C') Change(1,w[a[x].x],y);
else if(s[0]=='N')
{
if(x==y) continue;
while((f1=top[x])!=(f2=top[y]))
{
if(dep[f1]<dep[f2]) swap(x,y),swap(f1,f2);
Fan(1,w[f1],w[x]);
x=fa[f1];
}
if(dep[x]>dep[y]) swap(x,y);
Fan(1,w[x]+1,w[y]);
}
else
{
ans=-2147483647;
while((f1=top[x])!=(f2=top[y]))
{
if(dep[f1]<dep[f2]) swap(x,y),swap(f1,f2);
ans=max(ans,Max(1,w[f1],w[x]));
x=fa[f1];
}
if(dep[x]>dep[y]) swap(x,y);
ans=max(ans,Max(1,w[x]+1,w[y]));
printf("%d\n",ans);
}
}
}