本文共 5840 字，大约阅读时间需要 19 分钟。
包含若干行，每行一个整数。即对于输入中的每个询问，依次输出一个答案。
显然是用树链剖分+线段树，线段树维护连通性(最长路)。
维护连通性的方法和类似(建议先做一下bzoj1018再做这道题)。
#include #include #include #include #include #include #include #include #include #include #include #define ll long longusing namespace std;struct miku{ int luru; int ldrd; int lurd; int ldru; int lumx; int ldmx; int rumx; int rdmx; int l,r;}t[400010];int n,m;int x,y;int num;int tot;char c[4];char ch[4];int f[50010];int d[50010];int s[50010];int q[50010];int to[100010];int son[50010];int top[50010];int size[50010];int head[50010];int a[50010][4];int next[100010];void add(int x,int y){ tot++; next[tot]=head[x]; head[x]=tot; to[tot]=y;}void dfs(int x){ size[x]=1; d[x]=d[f[x]]+1; for(int i=head[x];i;i=next[i]) { if(to[i]!=f[x]) { f[to[i]]=x; dfs(to[i]); size[x]+=size[to[i]]; if(size[to[i]]>size[son[x]]) { son[x]=to[i]; } } }}void dfs2(int x,int tp){ top[x]=tp; s[x]=++num; q[num]=x; if(son[x]) { dfs2(son[x],tp); } for(int i=head[x];i;i=next[i]) { if(to[i]!=f[x]&&to[i]!=son[x]) { dfs2(to[i],to[i]); } }}void merge(miku &z,miku x,miku y){ z.l=x.l; z.r=y.r; z.luru=0; if(a[q[x.r]][1]&&a[q[y.l]][1]&&x.luru&&y.luru) { z.luru=max(x.luru+y.luru,z.luru); } if(a[q[x.r]][2]&&a[q[y.l]][2]&&x.lurd&&y.ldru) { z.luru=max(x.lurd+y.ldru,z.luru); } z.lurd=0; if(a[q[x.r]][1]&&a[q[y.l]][1]&&x.luru&&y.lurd) { z.lurd=max(x.luru+y.lurd,z.lurd); } if(a[q[x.r]][2]&&a[q[y.l]][2]&&x.lurd&&y.ldrd) { z.lurd=max(x.lurd+y.ldrd,z.lurd); } z.ldru=0; if(a[q[x.r]][1]&&a[q[y.l]][1]&&x.ldru&&y.luru) { z.ldru=max(x.ldru+y.luru,z.ldru); } if(a[q[x.r]][2]&&a[q[y.l]][2]&&x.ldrd&&y.ldru) { z.ldru=max(x.ldrd+y.ldru,z.ldru); } z.ldrd=0; if(a[q[x.r]][1]&&a[q[y.l]][1]&&x.ldru&&y.lurd) { z.ldrd=max(x.ldru+y.lurd,z.ldrd); } if(a[q[x.r]][2]&&a[q[y.l]][2]&&x.ldrd&&y.ldrd) { z.ldrd=max(x.ldrd+y.ldrd,z.ldrd); } z.lumx=x.lumx; if(a[q[x.r]][1]&&a[q[y.l]][1]&&x.luru) { z.lumx=max(x.luru+y.lumx,z.lumx); } if(a[q[x.r]][2]&&a[q[y.l]][2]&&x.lurd) { z.lumx=max(x.lurd+y.ldmx,z.lumx); } z.ldmx=x.ldmx; if(a[q[x.r]][1]&&a[q[y.l]][1]&&x.ldru) { z.ldmx=max(x.ldru+y.lumx,z.ldmx); } if(a[q[x.r]][2]&&a[q[y.l]][2]&&x.ldrd) { z.ldmx=max(x.ldrd+y.ldmx,z.ldmx); } z.rumx=y.rumx; if(a[q[x.r]][1]&&a[q[y.l]][1]&&y.luru) { z.rumx=max(y.luru+x.rumx,z.rumx); } if(a[q[x.r]][2]&&a[q[y.l]][2]&&y.ldru) { z.rumx=max(y.ldru+x.rdmx,z.rumx); } z.rdmx=y.rdmx; if(a[q[x.r]][1]&&a[q[y.l]][1]&&y.lurd) { z.rdmx=max(y.lurd+x.rumx,z.rdmx); } if(a[q[x.r]][2]&&a[q[y.l]][2]&&y.ldrd) { z.rdmx=max(y.ldrd+x.rdmx,z.rdmx); }}void build(int rt,int l,int r){ if(l==r) { t[rt].l=l; t[rt].r=r; if(a[q[l]][1]==1&&a[q[l]][2]==1) { t[rt].luru=t[rt].ldrd=1; t[rt].lurd=t[rt].ldru=2; t[rt].lumx=t[rt].ldmx=t[rt].rumx=t[rt].rdmx=2; } else if(a[q[l]][1]==1&&a[q[l]][2]==0) { t[rt].luru=t[rt].lumx=t[rt].rumx=1; } else if(a[q[l]][1]==0&&a[q[l]][2]==1) { t[rt].ldrd=t[rt].ldmx=t[rt].rdmx=1; } return ; } int mid=(l+r)>>1; build(rt<<1,l,mid); build(rt<<1|1,mid+1,r); merge(t[rt],t[rt<<1],t[rt<<1|1]);}void clear(miku &x){ x.luru=x.lurd=x.ldru=x.ldrd=0; x.lumx=x.ldmx=x.rumx=x.rdmx=0;}void change(int rt,int l,int r,int k){ if(l==r) { clear(t[rt]); if(a[q[l]][1]==1&&a[q[l]][2]==1) { t[rt].luru=t[rt].ldrd=1; t[rt].lurd=t[rt].ldru=2; t[rt].lumx=t[rt].ldmx=t[rt].rumx=t[rt].rdmx=2; } else if(a[q[l]][1]==1&&a[q[l]][2]==0) { t[rt].luru=t[rt].lumx=t[rt].rumx=1; } else if(a[q[l]][1]==0&&a[q[l]][2]==1) { t[rt].ldrd=t[rt].ldmx=t[rt].rdmx=1; } return ; } int mid=(l+r)>>1; if(k<=mid) { change(rt<<1,l,mid,k); } else { change(rt<<1|1,mid+1,r,k); } merge(t[rt],t[rt<<1],t[rt<<1|1]);}miku query(int rt,int l,int r,int L,int R){ if(L<=l&&r<=R) { return t[rt]; } int mid=(l+r)>>1; if(R<=mid) { return query(rt<<1,l,mid,L,R); } if(L>mid) { return query(rt<<1|1,mid+1,r,L,R); } miku res; merge(res,query(rt<<1,l,mid,L,R),query(rt<<1|1,mid+1,r,L,R)); return res; }void rotate(miku &x){ swap(x.lurd,x.ldru); swap(x.lumx,x.rumx); swap(x.ldmx,x.rdmx); swap(x.l,x.r);}int lca(int x,int y){ miku res; miku ans; clear(ans); clear(res); int tx=0; int ty=0; while(top[x]!=top[y]) { if(d[top[x]]>d[top[y]]) { if(tx==0) { res=query(1,1,n,s[top[x]],s[x]); tx=1; } else { merge(res,query(1,1,n,s[top[x]],s[x]),res); } x=f[top[x]]; } else { if(ty==0) { ans=query(1,1,n,s[top[y]],s[y]); ty=1; } else { merge(ans,query(1,1,n,s[top[y]],s[y]),ans); } y=f[top[y]]; } } if(d[x]
转载于:https://www.cnblogs.com/Khada-Jhin/p/9710786.html
