虚树
%自为风月马前卒巨佬%
用于优化一类树形DP问题。
当状态转移只和树中的某些关键点有关的时候，我们把这些点和它们两两之间的LCA弄出来，以点的祖孙关系连成一棵新的树，这就是虚树。
容易证明，如果关键点数量为\(m\)，则虚树点数不超过\(2m\)。
虚树的构建
dfs原树，对点进行dfn标号，并将关键点按dfn从小到大排序。
搞个栈，栈内的点满足：都在从栈顶的点到原树的根的一条链上。
现在我们准备加入一个点\(x\)
直接加可能破坏一条链的性质，于是把栈顶的元素弹掉直到可以加入为止。求个LCA讨论一波，具体参考代码。
弹栈的时候就可以连好虚树边了。
int p=0;//st[0]代表一个dfn为0的0号空点，方便处理
sort(a+1,a+m+1,cmp);//按dfn排序
for(int i=1;i<=m;st[++p]=a[i++]){
int y=lca(a[i],st[p]);
while(p&&dfn[st[p-1]]>=dfn[y])
add(st[p-1],st[p]),--p;
if(y!=st[p])add(y,st[p]),st[p]=y;//注意判断
}
while(p>1)add(st[p-1],st[p]),--p;//st[1]应为虚树根
当然，可能有些题的虚树在关键点之间也有限制？写出来都不一样。
比如洛谷P2495 [SDOI2011]消耗战
有一个固定的\(1\)号点，再就是只能保留没有祖孙关系（\(1\)号点除外）的关键点。写法也有好几处不一样
int p=0;st[0]=1;
sort(h+1,h+k+1,cmp);
for(R i=1;i<=k;++i){
if(!p){st[++p]=h[i];continue;}
R x=h[i],y=lca(x,st[p]);
if(y==st[p])continue;
while(p&&l[st[p-1]]>=l[y])add(st[p-1],st[p]),--p;
if(y!=st[p])add(y,st[p]),st[p]=y;
st[++p]=x;
}
while(p)add(st[p-1],st[p]),--p;
所以看来虚树这个东西关键不在于背板子，而在于灵活运用。
洛谷P3233 [HNOI2014]世界树
每个询问建虚树，两遍dfs确定每个虚树上的点被哪里管理（第一遍从下往上更新，第二遍从上往下）
对于两个虚树点中间的部分，倍增找出临界点，两边的size分开贡献。
找临界点是个极其恶心的讨论就对了。
倍增代码短常数大，表示基本没有看到别的小于2.5k的代码。。。
#include<bits/stdc++.h>
#define R register int
#define G if(++ip==ie)if(fread(ip=buf,1,SZ,stdin))
using namespace std;
const int SZ=1<<19,N=3e5+9,M=2*N;
char buf[SZ],*ie=buf+SZ,*ip=ie-1;
inline int in(){
G;while(*ip<'-')G;
R x=*ip&15;G;
while(*ip>'-'){x*=10;x+=*ip&15;G;}
return x;
}
int p,he[N],ne[M],to[M],l[N],sr[N],d[N],o[N],fa[N][20];
void dfs(R x,R f){
l[x]=++p;sr[x]=1;d[x]=d[f]+1;fa[x][0]=f;
for(R&i=o[x];(fa[x][i+1]=fa[fa[x][i]][i]);++i);
for(R i=he[x];i;i=ne[i])
if(to[i]!=f)dfs(to[i],x),sr[x]+=sr[to[i]];
}
int lca(R x,R y){
if(d[x]<d[y])swap(x,y);
for(R i=o[x];~i;--i)
if(d[fa[x][i]]>=d[y])x=fa[x][i];
if(x==y)return x;
for(R i=o[x];~i;--i)
if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
namespace VT{
int h[N],a[N],st[N],he[N],ne[N],tp[N],mn[N],id[N],si[N],ans[N],ok[N];
inline bool cmp(R x,R y){
return l[x]<l[y];
}
inline void add(R x,R y){
ne[y]=he[x];he[x]=tp[y]=y;
for(R i=0,k=d[y]-d[x]-1;k;k>>=1,++i)
if(k&1)tp[y]=fa[tp[y]][i];
}
inline void chkmn(R x,R y){
R t=mn[y]+abs(d[y]-d[x]);
if(mn[x]>t)mn[x]=t,id[x]=id[y];
else if(mn[x]==t&&h[id[x]]>h[id[y]])id[x]=id[y];
}
void calc(R x,R y){
R z=y,p=d[x]-mn[x]+d[y]+mn[y];
if(p&1)p=(p+1)>>1;
else p=(p>>1)+(h[id[x]]<h[id[y]]||mn[x]+d[x]==mn[y]+d[y]);
for(R i=0,k=d[y]-p;k;k>>=1,++i)
if(k&1)z=fa[z][i];
ans[id[y]]+=sr[z]-si[y];
ans[id[x]]+=sr[tp[y]]-sr[z];
he[y]=si[y]=0;
}
void dfsup(R x){
if(!ok[x])mn[x]=M;
for(R y=he[x];y;y=ne[y])
dfsup(y),chkmn(x,y),si[x]+=sr[tp[y]];
}
void dfsdn(R x){
for(R y=he[x];y;y=ne[y])
chkmn(y,x),dfsdn(y),calc(x,y);
}
void work(){
R m=in(),p=0;
for(R i=1;i<=m;++i){
R x=h[i]=a[i]=in();
mn[x]=0,id[x]=i,ok[x]=1;
}
sort(a+1,a+m+1,cmp);
for(R i=1;i<=m;st[++p]=a[i++]){
R y=lca(a[i],st[p]);
while(p&&l[st[p-1]]>=l[y])add(st[p-1],st[p]),--p;
if(y!=st[p])add(y,st[p]),st[p]=y;
}
while(p)add(st[p-1],st[p]),--p;
dfsup(0);dfsdn(0);he[0]=0;
for(R i=1;i<=m;++i)printf("%d ",ans[i]),ok[h[i]]=ans[i]=0;puts("");
}
}
int main(){
R n=in();to[he[0]=1]=1;
for(R i=1,p=1;i<n;++i){
R x=in(),y=in();
ne[++p]=he[x];to[he[x]=p]=y;
ne[++p]=he[y];to[he[y]=p]=x;
}
dfs(0,0);
for(R q=in();q;--q)VT::work();
return 0;
}
仙人掌
DFS树
就是Tarjan算法用的那种结构，边分成树边和返祖边。
放到仙人掌上就会有一个性质：返祖边覆盖的树边区间是没有交错重叠的。
那么，我们不用写Tarjan也可以很方便的知道那些点在一个环里。
于是已经可以解决一点点问题了。
BZOJ4316 小C的独立集
求仙人掌最大独立集
yyb说额外记一维表示环底下那个点的状态
蒟蒻觉得，先把环上其它子树都做完，放到环上，再单独取环底下那个点的两个状态分别在环上跑DP，也是挺吼的。
暂时BZOJ rank1
洛谷P2478 [SDOI2010]城市规划
仙人掌上选若干个点满足两两之间最短路\(>=3\)，最大化点权和。和带权最大独立集很像的。
每个点的状态有三个：自己选，儿子选，自己和儿子都不选。转移随便yy就好了，细节有一些，但应该还是不难。
环上DP应该要考虑最下面两个点，依据环底部点对环顶部点的影响（也就是环底部点离最近已选点的距离）分成三类。
然而这个题是个假题。。。
https://www.luogu.org/discuss/lists?forumname=P2478
https://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=1952
所以下面的代码蒟蒻也不能保证正确性
（蒟蒻的写法应该是可以适用于仙人掌而不局限于题面说的点至多在一个环上）
#include<bits/stdc++.h>
#define R register int
#define G if(++ip==ie)if(fread(ip=buf,1,SZ,stdin))
using namespace std;
const int SZ=1<<19,N=1e6+9,M=2*N,INF=-2e9;
char buf[SZ],*ie=buf+SZ,*ip=ie-1;
inline int in(){
G;while(*ip<'-')G;
R x=*ip&15;G;
while(*ip>'-'){x*=10;x+=*ip&15;G;}
return x;
}
int he[N],ne[M],to[M],fa[N],d[N];
struct Dat{
int f0,f1,f2;
inline void operator+=(const Dat&a){
f0=max(f0+max(a.f0,a.f1),f1+a.f2);
f1+=max(a.f0,a.f1);
f2+=a.f1;
}
}g[N];
void dp(R x,R f){
Dat now,lst,res=(Dat){0,0,0};R y=fa[x];
for(R op=0;op<3;++op){//x到已选点的最短路是op
switch(op){
case 0:now=(Dat){g[y].f1+g[x].f2,INF,INF};break;
case 1:now=(Dat){g[y].f0+g[x].f0,g[y].f1+g[x].f0,g[y].f2+g[x].f1};break;
case 2:now=(Dat){g[y].f0+g[x].f1,g[y].f1+g[x].f1,INF};
}
for(R y=fa[x];y!=f;y=fa[y])
lst=now,(now=g[fa[y]])+=lst;
switch(op){
case 2:res.f2=max(res.f2,now.f2);
case 1:res.f0=max(res.f0,now.f0);res.f1=max(res.f1,now.f1);break;
case 0:res.f0=max(res.f0,now.f1);
}
}
g[f]=res;
}
int dfs(R x,R f){
fa[x]=f;d[x]=d[f]+1;
R top=0;//环顶端
for(R i=he[x];i;i=ne[i]){
if(to[i]==f)continue;
if(d[to[i]]){
if(d[to[i]]>d[x])dp(to[i],x),top^=x;
else top^=to[i];
}
else top^=dfs(to[i],x);
}
if(!top)g[f]+=g[x];
return top;
}
int main(){
R n=in(),m=in(),ans=0;
for(R i=1;i<=n;++i)g[i].f2=in();
for(R i=1,p=0;i<=m;++i){
R x=in(),y=in();
ne[++p]=he[x];to[he[x]=p]=y;
ne[++p]=he[y];to[he[y]=p]=x;
}
for(R i=1;i<=n;++i)
if(!d[i])dfs(i,0),ans+=max(g[i].f0,max(g[i].f1,g[i].f2));
printf("%d\n",ans);
return 0;
}
洛谷P4244 [SHOI2008]仙人掌图 II
求仙人掌直径。
不在环上的记一下最大值和次大值转移即可。
对于环还是单独来一遍DP，破环为链，贡献答案的限制为两点距离不超过环长的一半，显然单调队列优化。
圆方树
专门用来优化仙人掌上的一些问题。
圆方树的点分为圆点和方点，圆点与原来仙人掌中的点一一对应，方点与仙人掌的每个环一一对应。
圆方树的边也有两种：
- 仙人掌中不在环上的边，在圆方树中保留。
- 每个方点向其对应的仙人掌环上的每一个点连一条边。
可以想象成，把仙人掌的所有环上的边抹去，环*建一个方点向四周放射状连边，就形成了圆方树。
另参考YL的总结，圆方树的另一种写法是，不在环上的边中间也强行插入一个方点。
或者说，把不在环上的边视为两条重边形成的环。
这样的圆方树会有一些更好的性质，比如任意路径上的圆点和方点相间。
BZOJ2125 最短路 or 洛谷P5236 【模板】静态仙人掌(圆方树)
仙人掌最短路，多组询问，不带修改。
因为环上两点的最短路可以直接算，所以建出圆方树：
- 不在环上的边不动；
- 方点的父亲是其对应环的顶端节点，边权为0。
- 在环上但不是顶端的节点的父亲是方点，边权为其到顶端节点的最短路。
每个询问在圆方树上求LCA：
- LCA是圆点，两点距离就是答案。
- LCA是方点，两点距离除掉顶上那两条边的边权，再加上环上最短路。
#include<bits/stdc++.h>
#define LL long long
#define R register int
#define G if(++ip==ie)if(fread(ip=buf,1,SZ,stdin))
using namespace std;
const int SZ=1<<19,N=3e4+9;
char buf[SZ],*ie=buf+SZ,*ip=ie-1;
inline int in(){
G;while(*ip<'-')G;
R x=*ip&15;G;
while(*ip>'-'){x*=10;x+=*ip&15;G;}
return x;
}
int n,he[N],ne[N],to[N],w[N],d[N],fa[N];
inline int calc(R x,R y,R len){//环上最短路
R r=abs(d[x]-d[y]);
return min(r,len-r);
}
namespace RST{
int he[N],ne[N],to[N],w[N],d[N],l[N],o[N],fa[N][15];
inline void add(R x,R y,R z){
ne[y]=he[x];he[x]=y;fa[y][0]=x;w[y]=z;
}
void dfs(R x){
for(R&i=o[x];(fa[x][i+1]=fa[fa[x][i]][i]);++i);
for(R y=he[x];y;y=ne[y])
d[y]=d[x]+1,w[y]+=w[x],dfs(y);
}
int qry(R x,R y){
if(d[x]<d[y])swap(x,y);
R r=w[x]+w[y];
for(R i=o[x];~i;--i)
if(d[fa[x][i]]>=d[y])x=fa[x][i];
if(x==y)return r-2*w[x];
for(R i=o[x];~i;--i)
if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
return l[fa[x][0]]?r+calc(x,y,l[fa[x][0]])-w[x]-w[y]:r-2*w[fa[x][0]];
}
}
void build(R x,R f,R len){
RST::l[++n]=len;
for(;x!=f;x=fa[x])
RST::add(n,x,calc(x,f,len));
RST::add(x,n,0);
}
int dfs(R x){
R top=0;
for(R y,i=he[x];i;i=ne[i]){
if((y=to[i])==fa[x])continue;
if(d[y]){
if(d[y]>d[x])build(y,x,d[y]-d[x]+w[i]),top^=x;
else top^=y;
}
else fa[y]=x,d[y]=d[x]+w[i],top^=dfs(y);
}
if(!top&&x!=1)RST::add(fa[x],x,d[x]-d[fa[x]]);
return top;
}
int main(){
n=in();R m=in(),q=in();
for(R p=0,i=1;i<=m;++i){
R x=in(),y=in();w[p+1]=w[p+2]=in();
ne[++p]=he[x];to[he[x]=p]=y;
ne[++p]=he[y];to[he[y]=p]=x;
}
d[1]=RST::d[1]=1;//防止一些边界情况
dfs(1);RST::dfs(1);
while(q--)
printf("%d\n",RST::qry(in(),in()));
return 0;
}
广义圆方树
将仙人掌的环对应一般图的点双，圆方树也就变成了广义圆方树。
写Tarjan求割点，把点双里的点压进栈里，一起连边后一起弹出来。
核心构建代码
void dfs(R x){
low[x]=dfn[x]=++df;st[++p]=x;
for(R y,i=he[x];i;i=ne[i])
if(dfn[y=to[i]])cmn(low[x],dfn[y]);
else{
dfs(y),cmn(low[x],low[y]);
if(low[y]==dfn[x]){
RST::add(x,++RST::n);R z;
do RST::add(RST::n,z=st[p--]);while(z!=y);
}
}
}
洛谷P4320 道路相遇（板子题）
欧拉路径
遍历整张图，不重不漏地经过每一条边的路径。如果起点终点相同则称作欧拉回路。
判断欧拉路、欧拉回路是否存在的充要条件：
无向图欧拉回路：所有点度数为偶数
有向图欧拉回路：所有点入度等于出度
无向图欧拉路：至多两点度数为奇数
有向图欧拉路：至多一点入度等于出度+1，一点入度等于出度-1，其它所有点入度等于出度
构造方法：dfs，每次访问一条未访问的边并打*问标记，回溯时将边加入答案数组，最后将数组倒序输出。
UOJ117 欧拉回路
#include<bits/stdc++.h>
#define LL long long
#define R register int
#define G if(++ip==ie)if(fread(ip=buf,1,SZ,stdin))
using namespace std;
const int SZ=1<<19,N=1e5+9,M=4*N;
char buf[SZ],*ie=buf+SZ,*ip=ie-1;
inline int in(){
G;while(*ip<'-')G;
R x=*ip&15;G;
while(*ip>'-'){x*=10;x+=*ip&15;G;}
return x;
}
int t,n,m,p,he[N],ne[M],to[M],d[N],ans[M];
bool vis[M];
void dfs1(R x){
for(R i=he[x];i;i=he[x]){
he[x]=ne[he[x]];
if(!vis[i]){
vis[i^1]=1;
dfs1(to[i]),ans[++p]=(i>>1)*(i&1?-1:1);
}
}
}
void dfs2(R x){
for(R i=he[x];i;i=he[x]){
he[x]=ne[he[x]];
dfs2(to[i]),ans[++p]=i;
}
}
int main(){
t=in(),n=in(),m=in();
for(R i=1,p=t&1;i<=m;++i){
R x=in(),y=in();
ne[++p]=he[x],to[he[x]=p]=y,++d[y];
if(t&1)ne[++p]=he[y],to[he[y]=p]=x,++d[x];
else --d[x];
}
for(R i=1;i<=n;++i)
if(t&1?d[i]&1:d[i])return puts("NO"),0;
for(R i=1;i<=n;++i)
if((t&1?dfs1:dfs2)(i),p)break;
if(p<m)return puts("NO"),0;
puts("YES");
for(R i=p;i;--i)printf("%d ",ans[i]);
puts("");
return 0;
}