头像

洛零


访客:1136

离线:6小时前



洛零
16小时前
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;
const int N=1e2+5,M=6e3+5,INF=1e9;
int n,m,s,t;
int head[N],to[M],nxt[M],val[M],cnt;
int d[N],cur[N],maxflow;

void add(int u,int v,int w) {
    to[++cnt]=v;
    val[cnt]=w;
    nxt[cnt]=head[u];
    head[u]=cnt;
}

bool bfs() {
    memset(d,0,sizeof(d));
    d[s]=1;
    queue<int> q;
    q.push(s);
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        cur[u]=head[u];
        for(int i=head[u];i;i=nxt[i]) {
            int v=to[i],w=val[i];
            if(!d[v] and w>0) {
                d[v]=d[u]+1;
                q.push(v);
                if(v==t)
                  return true;
            }
        } 
    }
    return false;
}

int dfs(int u,int lim) {
    if(u==t)
      return lim;
    int flow=0;
    for(int i=cur[u];i and flow<lim;i=nxt[i]) {
        int v=to[i],w=val[i];
        cur[u]=i;
        if(d[v]==d[u]+1 and w>0) {
            int k=dfs(v,min(lim-flow,w));
            if(!k)
              d[v]=-1;
            val[i]-=k;
            val[i^1]+=k;
            flow+=k;
        }
    }
    return flow;
}

int main() {
    cnt=1;
    cin>>n>>m;
    s=0;t=m+1;
    int u=0,v=0;
    for(int i=1;i<=n;i++) {
        add(s,i,1);
        add(i,s,0);
    }
    for(int i=n+1;i<=m;i++) {
        add(i,t,1);
        add(t,i,0);
    }
    while(cin>>u>>v,u!=-1) {
        add(u,v,1);
        add(v,u,0);
    }
    int flow;
    while(bfs())
      while(flow=dfs(s,INF)) 
        maxflow+=flow;
    cout<<maxflow<<endl;
    for(int i=1;i<=n;i++){
        for(int j=head[i];j;j=nxt[j]) {
            if(val[j]==0 and to[j]>=n+1 and to[j]<=m) {
                cout<<i<<' '<<to[j]<<endl;
                break;
            }
        }
    }
    return 0;
}




洛零
17小时前
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;
const int N=1e4+5,M=2e5+5,INF=1e9; 
int n,m,s,t;
int head[N],to[M],nxt[M],val[M],cnt;
int d[N],cur[N],maxflow;

void add(int u,int v,int w) {
    to[++cnt]=v;
    val[cnt]=w;
    nxt[cnt]=head[u];
    head[u]=cnt;
}

bool bfs() {
    memset(d,0,sizeof(d));
    queue<int> q;
    d[s]=1;
    q.push(s);
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        cur[u]=head[u];
        for(int i=head[u];i;i=nxt[i]) {
            int v=to[i],w=val[i];
            if(w>0 and !d[v]) {
                q.push(v);
                d[v]=d[u]+1;
                if(v==t)
                  return true;
            }
        }
    }
    return false;
}

int dfs(int u,int lim) {
    if(u==t)
      return lim;
    int flow=0;
    for(int i=cur[u];i and flow<lim;i=nxt[i]) {
        int v=to[i],w=val[i];
        cur[u]=i;
        if(d[v]==d[u]+1 and w>0) {
            int k=dfs(v,min(lim-flow,w));
            if(!k)
              d[v]=-1;
            val[i]-=k;
            val[i^1]+=k;
            flow+=k; 
        }
    }
    return flow;
}

int main() {
    cnt=1;
    cin>>n>>m>>s>>t;
    while(m--) {
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,0);
    }
    int flow;
    while(bfs())
      while(flow=dfs(s,INF))
        maxflow+=flow;
    cout<<maxflow;
    return 0;
}




洛零
1天前

首先,如果一个流的残量网络里面没有可行流,那么这个流就是最大流。
EK算法就是基于这个事实的算法,时间复杂度为$O(nm^2)$(n为点数m为边数)。
详细地讲,过程如下:
- 1、找增广路
- 2、更新残量网络增广路上的流量
- 3、重复执行1、2直到网络里没有增广路

对于边与反向边的话,我们使用“成对存储”的技巧来存,这样访问反向边就很方便了。
然后找增广路的过程中需要记录经过的边,以便于之后更新。
请注意cnt初值为1,极其容易写错。

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;
const int N=1e3+5,M=2e4+5,INF=1e9;  //因为我们维护残留网络,所以要建反向边,边数*2
int n,m,s,t;    //点数,边数,源点,汇点
int head[N],to[M],nxt[M],val[M],cnt;    //链式前向星
int pre[N],inc[N],maxflow;  
//pre[i]表示bfs里,到点i的边的编号
//inc表示源点到当前点的流量
//maxflow即最大流
bool vis[N];    //记录点有没有被访问过

void add(int u,int v,int w) {   //链式前向星加边
    to[++cnt]=v;
    val[cnt]=w;
    nxt[cnt]=head[u];
    head[u]=cnt;
}

bool bfs() {    //找一条增广路
    memset(vis,0,sizeof(vis));  //清空vis数组
    queue<int> q;   //bfs的队列
    q.push(s);
    inc[s]=INF; //源点的流量即无穷大
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=nxt[i]) {
            int v=to[i],w=val[i];
            if(w>0 and !vis[v]) {   //边权大于0(即增广路)
                inc[v]=min(inc[u],w);   //流量为边权与inc[u]的最小值(可以理解为一部分水流被这条管道挡住了)
                q.push(v);
                vis[v]=true;
                pre[v]=i;   //记录前向边
                if(v==t)    //有增广路了
                  return true;
            }
        }
    }
    return false;   //找不到增广路
}

void update() {
    int p=t;    //由于我们是反向存边,所以说需要从汇点往源点走
    while(p!=s) {
        val[pre[p]]-=inc[t];    //残量网络的定义
        val[pre[p]^1]+=inc[t];  //i^1即i的反向边
        p=to[pre[p]^1]; //往前走
    }
    maxflow+=inc[t];    //最大流加上当前增广路到汇点的流量
}

int main() {
    cnt=1;  //重要!网络流里面的所有cnt都从1开始,来成对存储!
    cin>>n>>m>>s>>t;
    while(m--) {
        int u,v,w;
        cin>>u>>v>>w;
        //直接建立残量网络
        add(u,v,w);
        add(v,u,0);
    }
    //EK算法的核心
    while(bfs())    //一直找增广路
      update(); //更新权值,并增加最大流
    cout<<maxflow;  //输出最大流
    return 0;
}


活动打卡代码 AcWing 2171. EK求最大流

洛零
1天前
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;
const int N=1e3+5,M=2e4+5,INF=1e9; 
int n,m,s,t;
int head[N],to[M],nxt[M],val[M],cnt;
int pre[N],inc[N],maxflow;
bool vis[N];

void add(int u,int v,int w) {
    to[++cnt]=v;
    val[cnt]=w;
    nxt[cnt]=head[u];
    head[u]=cnt;
}

bool bfs() {
    memset(vis,0,sizeof(vis));
    queue<int> q;
    q.push(s);
    inc[s]=INF;
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=nxt[i]) {
            int v=to[i],w=val[i];
            if(w>0 and !vis[v]) {
                inc[v]=min(inc[u],w);
                q.push(v);
                vis[v]=true;
                pre[v]=i;
                if(v==t)
                  return true;
            }
        }
    }
    return false;
}

void update() {
    int p=t;
    while(p!=s) {
        val[pre[p]]-=inc[t];
        val[pre[p]^1]+=inc[t];
        p=to[pre[p]^1];
    }
    maxflow+=inc[t];
}

int main() {
    cnt=1;
    cin>>n>>m>>s>>t;
    while(m--) {
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,0);
    }
    while(bfs())
      update();
    cout<<maxflow;
    return 0;
}



活动打卡代码 AcWing 311. 月之谜

洛零
2天前
#include <cstdio>
#include <cstring>

using namespace std;
typedef unsigned long long ll;
const int N=202;
ll l,r;
ll a[21],f[21][N][N];
ll sum;

ll dp(int eq,int dep,int cur,int mod) {
    if(cur>sum)
      return 0;
    if(!dep)
      return (mod==0 and cur==sum);
    if((!eq) and (~f[dep][cur][mod]))
      return f[dep][cur][mod];
    int ed=(eq)?a[dep]:9;
    ll ret=0;
    for(int i=0;i<=ed;i++)
      ret+=dp(eq and (i==ed),dep-1,cur+i,(mod*10+i)%sum);
    if(!eq)
      f[dep][cur][mod]=ret;
    return ret;  
}

ll work(ll n) {
    a[0]=0;
    for(;n;n/=10)
      a[++a[0]]=n%10;
    ll ret=0;
    for(int i=1;i<=a[0]*9;i++) {
        sum=i;
        memset(f,-1,sizeof(f));
        ret+=dp(1,a[0],0,0);
    }
    return ret;
}

int main() {
    scanf("%llu%llu",&l,&r);
    printf("%llu",work(r)-work(l-1));
    return 0;
}



分享 树形dp

洛零
4天前

前言

树形dp是一种在树上做的dp,通常的结构为:

void dp(int u) {
    v[u]=true;
    for(int i=head[u];i;i=nxt[i]) {
        int v=to[i];
        dfs(v);
        update(f[u],f[v]);  //用f[v]来更新f[u]
    }
}

先递归子节点,再从子节点向上转移,这样就是一般的树形dp。

树直径

考虑这样一道题:
给定一棵无根树,求两个距离最远的节点间的距离,两个相邻结点距离为1。
首先,两个距离最远的结点必定是“边界点”,即度为1的点。
我们不妨对于每个点,求出这个点到这个点的子树的所有边界点的最长距离与次长距离,设为f[x][1],f[x][2],那么答案也就自然是$\max_{1\leq i\leq n}(f[i][1]+f[i][2])$
主要的瓶颈就在于:如何求出每个点的f呢?
我们看下dp代码

void dfs(int u) {
    v[u]=true;
    for(int i=head[u];i;i=nxt[i]) {
        int y=to[i];
        if(v[y])    //已经访问过了(即父节点),跳过
          continue;
        dfs(y); //递归子节点
        //以下代码请好好斟酌
        if(h[u][1]<=h[y][1]+1) {    //如果最长路可以更新
            h[u][2]=h[u][1];    //将次长路更新为最长路
            h[u][1]=h[y][1]+1;  //将最长路更新为新值
        }
        else if(h[u][2]<=h[y][1]+1) //如果次长路可以更新
          h[u][2]=h[y][1]+1;    //更新次长路
    }
}

因为这个树是一个无根树,所以我们从任意一个点开始执行dfs都可以。

树上背包问题

CTSC1997 选课

题目链接:选课acwing286
这n门课构成了一个森林的结构,为了简便,可以添加零号节点为各个树根的父亲,方便dp。
状态定义:f[u][t]表示在以u为根的子树中选t门的最高得分。
状态的转移实际上是一个分组背包模型,一个点的所有子节点看做是一组物品v,每组物品有f[v][i]的价值与i的消费。每组物品中只能取一个。

#include <iostream>
#include <cstring>

using namespace std;
const int N=3e2+5;
int n,m;
int head[N],to[N],nxt[N],cnt;
int score[N];
int f[N][N];

void add(int u,int v) {
    to[++cnt]=v;
    nxt[cnt]=head[u];
    head[u]=cnt;
}


void dp(int u) {
    f[u][0]=0;
    for(int i=head[u];i;i=nxt[i]) {
        int v=to[i];
        dp(v);
        for(int t=m;t>=0;t--)   //背包状态转移
          for(int j=t;j>=0;j--)
            f[u][t]=max(f[u][t],f[u][t-j]+f[v][j]);
    }
    if(u!=0)
      for(int i=m;i>0;i--)
        f[u][i]=f[u][i-1]+score[u];
}

int main() {
    memset(f,0xc0,sizeof(f));
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
        int u;
        cin>>u>>score[i];
        add(u,i);
    }
    dp(0);
    cout<<f[0][m];
    return 0;
}

二叉苹果树

题目链接:二叉苹果树
有了上面一道题,这道题就更加简单了,直接看代码。
注意不同的是,这道题是边权,上一题是点权。

#include <iostream>
#include <cstring>

using namespace std;
const int N=3e2+5;
int n,m;
int head[N],to[N],val[N],nxt[N],cnt;
bool vis[N];
int f[N][N];

void add(int u,int v,int w) {
    to[++cnt]=v;
    val[cnt]=w;
    nxt[cnt]=head[u];
    head[u]=cnt;
}

void dp(int u) {
    vis[u]=true;
    f[u][0]=0;
    for(int i=head[u];i;i=nxt[i]) {
        int v=to[i],w=val[i];
        if(vis[v])
          continue;
        dp(v);
        for(int t=m;t>=0;t--)
          for(int j=t;j>=0;j--)
            f[u][t]=max(f[u][t],f[u][t-j-1]+f[v][j]+w); //此处减一是要把自己算上去
    }
}

int main() {
    memset(f,0xc0,sizeof(f));
    cin>>n>>m;
    for(int i=1;i<n;i++) {
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);
    }
    dp(1);
    cout<<f[1][m];
    return 0;
}

典型树形dp

没有上司的舞会

题目链接:没有上司的舞会acwing285
状态定义:f[u][0]表示当u不选时,u的子树的最大值,f[u][1]表示选u时,u的最大值。
那么很容易写出状态转移方程了。

#include <iostream>
#include <cstdio>

using namespace std;
const int N=2e4+5;
int head[N],nxt[N],to[N],cnt;
int f[N][2],h[N],n,root,in[N];

void add(int u,int v) {
    to[++cnt]=v;
    nxt[cnt]=head[u];
    head[u]=cnt;
}

void dp(int p) {
    f[p][0]=0;
    f[p][1]=h[p];
    for(int i=head[p];i;i=nxt[i]) {
        int y=to[i];
        dp(y);  //这边要注意:如果有明确的依赖关系,就不需要判断是否为父亲,建边时建单向边即可。但是如果只是说有一条边,那么就要双向建边,并判断到达点是否为当前点的父亲
        f[p][0]+=max(f[y][1],f[y][0]);  //如果当前点不选,它的下级既可以选也可以不选
        f[p][1]+=f[y][0];   //如果当前点选,那么只有不选它的下级
    }
}

int main() {
    cin>>n;
    for(int i=1;i<=n;i++)
      cin>>h[i];
    for(int i=1;i<n;i++) {
        int u,v;
        cin>>u>>v;
        add(v,u);
        in[u]++;    //记录入度,根的入度必定为0
    }
    for(int i=1;i<=n;i++)
      if(in[i]==0) {
        root=i;
        break;
      }
    dp(root);   //从根开始dp
    cout<<max(f[root][0],f[root][1]);   //选根与不选根取最大值
    return 0;
}

数字转换

题目链接:数字转换
看起来不像树形dp,但我们可以把它转化成数形dp
设一个数x的约数和叫d[x],那么对于每个x我们不妨看做是x到d[x]连一条边。最后求这棵树的直径就行了。

#include <iostream>
#include <cstdio>

using namespace std;
const int N=4e5+5;
int n,m;
int head[N],to[N],nxt[N],cnt;
bool v[N];
int h[N][3],ans;
int sum[N];

void add(int u,int v) {
    to[++cnt]=v;
    nxt[cnt]=head[u];
    head[u]=cnt;
}

//求直径传统艺能
void dfs(int u) {
    v[u]=true;
    for(int i=head[u];i;i=nxt[i]) {
        int y=to[i];
        if(v[y]) 
          continue;
        dfs(y);
        if(h[u][1]<=h[y][1]+1) {
            h[u][2]=h[u][1];
            h[u][1]=h[y][1]+1;
        }
        else if(h[u][2]<=h[y][1]+1)
          h[u][2]=h[y][1]+1; 
    }
}

int main() {
    cin>>n;
    //求每个数的约数和并加边
    for(int i=1;i<=n;i++) { //枚举因子来求约数和
        if(sum[i]<i) {  //约数和小于原数
            add(i,sum[i]);  //加两条边
            add(sum[i],i);
        }
        for(int j=i*2;j<=n;j+=i)    //枚举i的倍数
          sum[j]+=i;
    }
    dfs(1);
    for(int i=1;i<=n;i++)
      ans=max(ans,h[i][1]+h[i][2]); //直径
    cout<<ans;
    return 0;
}

二次扫描与换根法

如果题目中要对每个点都进行统计,并且这棵树是无根树,那么就可以使用这个方法。
1、第一次扫描,任选一个点为根,执行从下到上的dp
2、第二次扫描,以刚才那个点为根,进行从上到下的推导
我们可以解决比如:求每个点到任意点的最长路,或者次长路等的问题。

Accumulation Degree

这道题目蓝书上面有讲解,就不赘述了。



活动打卡代码 AcWing 286. 选课

洛零
5天前
#include <iostream>
#include <cstring>

using namespace std;
const int N=3e2+5;
int n,m;
int head[N],to[N],nxt[N],cnt;
int score[N];
int f[N][N];

void add(int u,int v) {
    to[++cnt]=v;
    nxt[cnt]=head[u];
    head[u]=cnt;
}


void dp(int u) {
    f[u][0]=0;
    for(int i=head[u];i;i=nxt[i]) {
        int v=to[i];
        dp(v);
        for(int t=m;t>=0;t--)
          for(int j=t;j>=0;j--)
            f[u][t]=max(f[u][t],f[u][t-j]+f[v][j]);
    }
    if(u!=0)
      for(int i=m;i>0;i--)
        f[u][i]=f[u][i-1]+score[u];
}

int main() {
    memset(f,0xc0,sizeof(f));
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
        int u;
        cin>>u>>score[i];
        add(u,i);
    }
    dp(0);
    cout<<f[0][m];
    return 0;
}



分享 树上莫队

洛零
5天前

前言

树上莫队可以在树上查询一些很有意思的东西,比如众数、数的出现次数。
在阅读这篇文章之前,请确保你会基本的莫队以及欧拉序

一些概念

众所周知莫队是在序列上进行一系列的查询的,并且必须离线与静态(当然后人也发明出了带修莫队与在线莫队)。那么我们就不妨考虑将一棵树转为一个序列,再在这个序列上进行我们想要的操作。
这个序列就是欧拉序。

树上莫队

以这张图为我们的树,比如每次查询从uv的路径。

如果以1为根,欧拉序为1 2 4 4 5 6 6 5 3 7 7 3 1
那么每次询问就要把ein小的点放在前面,这样才好进行查询。
写成代码即

if(ein[u]>ein[v])
  swap(u,v);

这样就保证了uv在欧拉序上是有序的。
我们分两种路径关系来讨论。

直线型路径

就是一个点是另一个点的祖先的路径称为直线型路径(因为在树上是一条直线,比如从1–5)。
对于直线型路径,我们可以将其看做是[ein[u],ein[v]]这个序列的区间。
区间内有许多出现了两次的点,那么出现两次我们就不把它统计进去就好了。

折线型路径

如果两个点没有任何关系,lca不为两个点其中之一。那么我们将它看做是[eout[u],ein[v]]这个区间。与直线型相同,出现两次的点不统计。
但是。。。我们没有统计LCA?怎么办?
统计进去就行了呗。
可以对着上面那张图模拟一通。

例题&代码

我们虽然知道了树上莫队是什么,但是怎么写出来还是需要一些技巧的。
SP10707 COT2 - Count on a tree II
数颜色,一看就不是什么好东西。
果断选择莫队。
AC代码:

#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;
const int N=5e5+5;
int n,m,col[N]; //点数与询问数 
int b[N];
int head[N],to[N],nxt[N],cnt;   //链式前向星 
int siz,ans[N],res,a[N],pos[N]; //莫队 
int ein[N],eout[N],eular[N],tot;    //欧拉序 
int f[N][21],h,d[N];    //LCA 
bool sgn[N];    //重复访问

struct Q {  //莫队的询问 
    int l,r;
    int idx;
    int anc;
}q[N];

bool cmp(Q a,Q b) {     //压行的排序
    return pos[a.l]==pos[b.l]?pos[a.r]<pos[b.r]:pos[a.l]<pos[b.l];
} 

void add(int u,int v) {
    to[++cnt]=v;
    nxt[cnt]=head[u];
    head[u]=cnt;
}

void dfs(int u,int fa) {    //传统艺能
    f[u][0]=fa;
    for(int i=1;i<=h;i++)
      f[u][i]=f[f[u][i-1]][i-1];
    d[u]=d[fa]+1;
    eular[++tot]=u;
    ein[u]=tot;
    for(int i=head[u];i;i=nxt[i]) {
        int v=to[i];
        if(fa!=v)
          dfs(v,u);
    }
    eular[++tot]=u;
    eout[u]=tot;
} 

bool up(int u,int v) {
    return ein[u]<=ein[v] and eout[u]>=eout[v]; //传统艺能 
}

void update(int x) {    //莫队的更新结点
    if(sgn[x])  //如果这个点被更新过
      res-=(--a[col[x]]==0);
    else
      res+=(++a[col[x]]==1);
    sgn[x]^=1;  //取反
}

int lca(int x,int y) {  //传统艺能
    if(up(x,y))
      return x;
    if(up(y,x))
      return y;
    for(int i=h;i>=0;i--)
      if(!up(f[x][i],y) and f[x][i]!=0)
        x=f[x][i];
    return f[x][0];
}

int main() {
    //这边都用的是c输入输出,因为这题太卡常
    scanf("%d%d",&n,&m);
    siz=sqrt(m)+1;  //每块大小
    h=log(n)/log(2)+1;  //树高度
    for(int i=1;i<=n;i++) {
        scanf("%d",&b[i]);
        col[i]=b[i];
    }
    //这里需要离散化,不然桶开不到那么大,我之前就RE了好几次
    sort(b+1,b+n+1);
    for(int i=1;i<=n;i++)
      col[i]=lower_bound(b+1,b+n+1,col[i])-b;
    //建树
    for(int i=1;i<n;i++) {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    //分块
    for(int i=1;i<=2*n;i++)
      pos[i]=i/siz+1;
    dfs(1,0);
    //读入询问
    for(int i=1;i<=m;i++) {
        int u,v;
        scanf("%d%d",&u,&v);
        q[i].idx=i;
        q[i].anc=lca(u,v);  //记录下lca
        if(ein[u]>ein[v])   //将uv变有序
          swap(u,v);
        if(q[i].anc==u) {
            q[i].l=ein[u];
            q[i].r=ein[v];
            q[i].anc=0;     //直线型无需统计lca
        }
        else {
            q[i].l=eout[u];
            q[i].r=ein[v];
        }
    }
    //将询问排序
    sort(q+1,q+m+1,cmp);
    //处理询问
    int l=1,r=0;
    for(int i=1;i<=m;i++) {
        while(q[i].l<l) update(eular[--l]);
        while(q[i].r>r) update(eular[++r]);
        while(q[i].l>l) update(eular[l++]);
        while(q[i].r<r) update(eular[r--]);
        if(q[i].anc) update(q[i].anc);  //折线型没统计LCA
        ans[q[i].idx]=res;
        if(q[i].anc) update(q[i].anc);  //统计完,删掉
    }
    for(int i=1;i<=m;i++)
      printf("%d\n",ans[i]);    //输出
    return 0;
}



洛零
6天前

前言

欧拉序其实是一个很好用的东西,可以方便地求一些树上位置关系。
但是为什么没人用呢?

一、什么是欧拉序

欧拉序是在将一棵树转为一个序列,这个序列就叫欧拉序。
从根结点开始进行深度优先搜索,对于每个结点,入栈时和出栈时都记录一次。
例如下面这棵以1为根的树:

它的欧拉序为:123325665441,长度为2n

二、欧拉序判定树上位置关系

下面,我们以模板题祖孙询问来说明欧拉序如何判断位置关系。
对于每个点,我们开两个数组eineout来记录每个点的入栈和出栈时在欧拉序中是第几个。
还是以上图为例,那么
ein:1 2 3 10 6 7
eout:12 5 4 11 9 8
不难发现,一个点xy的祖先,当且仅当xy早入栈且xy晚出栈。
ein[x]<=ein[y] and eout[x]>=eout[y]
这里用了等于是如果x=y了,那么也算是祖先,避免了这种情况。
于是程序就很容易写出来了:

#include <iostream>
#include <cstdio>

using namespace std;
const int N=1e5+5;

int n,m;
int head[N],to[N],nxt[N],cnt;
int ein[N],eout[N],tot,root;

void add(int x,int y) { //链式前向星
    to[++cnt]=y;
    nxt[cnt]=head[x];
    head[x]=cnt;
}

void dfs(int x) {
    ein[x]=++tot;   //tot用了计数,这里记录下x的入栈时间
    for(int i=head[x];i;i=nxt[i]) {
        int y=to[i];
        if(!ein[y]) //如果y没访问过,就dfs(y)
          dfs(y);
    }
    eout[x]=++tot;  //记录x的出栈时间
}

bool up(int x,int y) {  //即上面的那串代码
    return (ein[x]<=ein[y] and eout[x]>=eout[y]);
}

int main() {
    cin>>n;
    for(int i=1;i<=n;i++) {
        int x,y;
        cin>>x>>y;
        if(y!=-1) {     //判断根结点
            add(x,y);
            add(y,x); 
        }
        else root=x;
    }
    dfs(root);  //生成欧拉序
    cin>>m;
    while(m--) {
        int x,y;
        cin>>x>>y;
        if(up(x,y))     //x是y的祖先
          cout<<1<<endl;
        else if(up(y,x))    //y是x的祖先
          cout<<2<<endl;
        else
          cout<<0<<endl;
    }
    return 0;
}

并且,这个程序的时间复杂度是$O(n+m)$比求LCA判定祖孙关系的时间复杂度$O(mlogn)$要好很多(如果你用tarjan求LCA当我没说,但个人觉得tarjan常数比欧拉序要大)。

三、LCA的写法

1、欧拉序+ST表

众所周知LCA是倍增来写的,其实还可以用欧拉序+ST表来实现,单次询问时间复杂度是$O(1)$的,比对数要快。
但因为写起来有点麻烦,就不写了。

2、倍增+祖孙判定

当然欧拉序可能更加帮你容易懂倍增LCA,它是这样子来写的。
我们先看预处理的部分

void dfs(int x,int fa) {    //x的父亲是fa结点
    f[x][0]=fa;
    for(int i=1;i<=h;i++)   //预处理倍增数组,这个少不了
      f[x][i]=f[f[x][i-1]][i-1];
    d[x]=d[fa]+1;
    //求欧拉序每个点的进出时间
    ein[x]=++tot;
    for(int i=head[x];i;i=nxt[i]) {
        int y=to[i];
        if(y!=fa)
          dfs(y,x);
    }
    eout[x]=++tot;
}

然后就是LCA了

int lca(int x,int y) {
    //两种特殊情况
    if(up(x,y))
      return x;
    if(up(y,x))
      return y;
    for(int i=h;i>=0;i--)
      if(!up(f[x][i],y) and f[x][i]!=0) //如果不是祖先,又不是0号结点
        x=f[x][i];  //往上跳
    return f[x][0]; //最后x的父亲必定是x与y的LCA
}

用祖孙判定+倍增来写是何等的简洁!比一起跳的那种倍增LCA要易懂得多(个人这么认为)。
点的距离AC代码

#include <iostream>
#include <cmath>

using namespace std;
const int N=2e5+5;

int n,m,h;
int head[N],to[N],nxt[N],cnt;
int ein[N],eout[N],tot;
int d[N],f[N][21];

void add(int x,int y) {
    to[++cnt]=y;
    nxt[cnt]=head[x];
    head[x]=cnt;
}

void dfs(int x,int fa) {
    f[x][0]=fa;
    for(int i=1;i<=h;i++)
      f[x][i]=f[f[x][i-1]][i-1];
    d[x]=d[fa]+1;   //树上前缀和
    ein[x]=++tot;
    for(int i=head[x];i;i=nxt[i]) {
        int y=to[i];
        if(y!=fa)
          dfs(y,x);
    }
    eout[x]=++tot;
}

bool up(int x,int y) {
    return (ein[x]<=ein[y] and eout[x]>=eout[y]);
}

int lca(int x,int y) {
    if(up(x,y))
      return x;
    if(up(y,x))
      return y;
    for(int i=h;i>=0;i--)
      if(!up(f[x][i],y) and f[x][i]!=0)
        x=f[x][i];
    return f[x][0];
}

int main() {
    cin>>n;
    h=log(n)/log(2)+1;  //深度
    for(int i=1;i<n;i++) {
        int x,y;
        cin>>x>>y;
        add(x,y);
        add(y,x); 
    }
    dfs(1,0);   //处理欧拉序
    cin>>m;
    while(m--) {
        int x,y;
        cin>>x>>y;
        cout<<d[x]+d[y]-2*d[lca(x,y)]<<endl;
    }
    return 0;
}

四、换根

这种欧拉序就比较神奇了,它是每经过一个点就记录一次,所以说可能一个点的次数不止两次。

还是以刚才那张图为例,这样子以1为根的欧拉序为:12321565141
这种欧拉序有着“循环”的功能,我们不妨将这串欧拉序延长一倍:123215651412321565141
那么换做是以5为根呢?欧拉序为刚才那个两倍串中标粗的一段:123215651412321565141
不管你换成以哪个点为根,都是一样的。所以就可以很方便地求解一些换根的操作啦。
但是程序实现较困难,所以就不写了qwq。



活动打卡代码 AcWing 352. 闇の連鎖

洛零
6天前
#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;
const int N=1e5+5,M=2e5+5;
int n,m;
int head[N],to[M],nxt[M],cnt;
int ein[N],eout[N],tot;
int b[N],ans;
int h,f[N][21];
bool vis[N];

void add(int u,int v) {
    to[++cnt]=v;
    nxt[cnt]=head[u];
    head[u]=cnt;
}

void dfs(int u,int fa) {
    ein[u]=++tot;
    f[u][0]=fa;
    for(int i=1;i<=h;i++)
      f[u][i]=f[f[u][i-1]][i-1];
    for(int i=head[u];i;i=nxt[i]) {
        int v=to[i];
        if(fa==v)
          continue;
        dfs(v,u);
    }
    eout[u]=++tot;
}

bool up(int u,int v) {
    return ein[u]<=ein[v] and eout[u]>=eout[v];
}

int lca(int u,int v) {
    if(up(u,v))
      return u;
    if(up(v,u))
      return v;
    for(int i=h;i>=0;i--)
      if(!up(f[u][i],v) and f[u][i]!=0)
        u=f[u][i];
    return f[u][0];
}

void search(int u) {
    vis[u]=true;
    for(int i=head[u];i;i=nxt[i]) {
        int v=to[i];
        if(vis[v])
          continue;
        search(v);
        b[u]+=b[v];
        if(b[v]==0)
          ans+=m;
        if(b[v]==1)
          ans++;
    }
}

int main() {
    cin>>n>>m;
    h=log(n)/log(2);
    for(int i=1;i<n;i++) {
        int u,v;
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    dfs(1,0);
    for(int i=1;i<=m;i++) {
        int u,v;
        cin>>u>>v;
        b[u]++;
        b[v]++;
        b[lca(u,v)]-=2;
    } 
    search(1);
    cout<<ans;
    return 0;
}