当前位置：首页 > news >正文

树上差分+lca 黑暗的锁链

news 来源：原创 2024/9/24 3:58:26

//** 太久不写了，感觉很难受。。。比赛最近打得也不好，课内任务又重，还要忙着做项目。何去何从。

今天又写了一题，用了树上差分的知识。下面来整理整理。

1.首先让我们学一下lca（最小公共父节点）

我用的是倍增来求的。总共其实就是两步：dfs打ST表预处理每个点的上面节点 lca求两点最小公共节点。lca里用了类似dp的思想。首先要知道dep[i][j]表示 i点向上跳1<<j个点后到达的点。然后想出递推关系式：dep[i][j]=dep[dep[i][j-1]][j-1]。用dfs来递推实现即可。

lca的实现其实就是 1.先将两个点化为同一层的点

2.寻找那一层的父节点是一样的

下面来看一下代码~

//倍增法求最近公共祖先LCA
#include<iostream>
using namespace std;int n,m;struct EDGE{int u,v,l;EDGE* ne;
}edge[100010];struct NODE{EDGE* fir;
}node[100010];int tot;
void my_build(int u,int v,int l){edge[tot].u=u;edge[tot].v=v;edge[tot].l=l;edge[tot].ne=node[u].fir;node[u].fir=&edge[tot];tot++;
}int ce[100010],dep[100010][20];//ce表示每个点的层数  dep[i][j]表示从第i个点向上走 1<<j (2^j) 个点到达的点位置；
/*
dep[i][j]=dep[dep[i][j-1]][j-1];  递推关系式
*/
void dfs(int u,int f){//打ST表   复杂度：nlognce[u]=ce[f]+1;dep[u][0]=f;for(int i=1;i<=19;i++){dep[u][i]=dep[dep[u][i-1]][i-1];//类似dp}EDGE* i=node[u].fir;while(i!=NULL){if(i->v==f){i=i->ne;continue;}dfs(i->v,u);i=i->ne;}
}int lca(int u,int v){  //LCA   复杂度：lognif(ce[u]<ce[v]){swap(u,v);}for(int i=19;i>=0;i--){if(ce[dep[u][i]]>=ce[v]){u=dep[u][i];}}if(u==v)return u;for(int i=19;i>=0;i--){if(dep[u][i]!=dep[v][i]){u=dep[u][i];v=dep[v][i];}}return dep[u][0];
}int main()
{cin>>n>>m;//建边之类...略；return 0;
}

2.树上差分

树上差分分两种：1.给点差分 2.给边差分

对应着两种不一样的题意：给点操作还是给边操作。

给点操作很好理解，就是每个点加加减减。但如果要给边操作，我们无法轻松表示边呐，so我们就以点代边，每个点表示其与父节点连接的边。

看一下操纵吧~

//给每个点做差分：例如 给u->v路径上所有点+1：sum[u]++; sum[v]++; sum[lca]-=2;
//给边做差分->归结到给点做差分：sum[u]++; sum[v]++; sum[lca]-=1; sum[fa[lca]]-=1;//差分数组求前缀和：
void my_add(int u,int fa){//差分数组求前缀和；EDGE* i=node[u].fir;while(i!=NULL){if(i->v==fa){i=i->ne;continue;}dfs(i->v,u);sum[u]+=sum[i->v];i=i->ne;}
}//差分数组：(以给边差分为例)
while(m--){cin>>u>>v;int l=lca(u,v);sum[u]++;sum[v]++;sum[l]--;sum[dep[l][0]]--;
}

3.看题目

问题：黑暗的锁链

题目描述

传说中的暗之连锁被人们称为Dark。Dark是人类内心的黑暗的产物，古今中外的勇者们都试图打倒它。经过研究，你发现Dark呈现无向图的结构，图中有N个节点和两类边，一类边被称为主要边，而另一类被称为附加边。Dark有N–1条主要边，并且Dark的任意两个节点之间都存在一条只由主要边构成的路径。另外，Dark还有M条附加边。
你的任务是把Dark斩为不连通的两部分。一开始Dark的附加边都处于无敌状态，你只能选择一条主要边切断。一旦你切断了一条主要边，Dark就会进入防御模式，主要边会变为无敌的而附加边可以被切断。但是你的能力只能再切断Dark的一条附加边。现在你想要知道，一共有多少种方案可以击败Dark。注意，就算你第一步切断主要边之后就已经把Dark斩为两截，你也需要切断一条附加边才算击败了Dark。

输入

第一行包含两个整数N和M。
之后N–1行，每行包括两个整数A和B，表示A和B之间有一条主要边。
之后M行以同样的格式给出附加边。

输出

输出一个整数表示答案。

样例输入 Copy

样例输出 Copy

提示

对于20%的数据，N≤100，M≤100。
对于100%的数据，N≤100000，M≤200000。数据保证答案不超过231–1。

这题用的就是树上差分+lca。而且是面向边的树上差分（因为是要切边）。

看代码~

#include<iostream>
using namespace std;
#define int long long int n,m;struct EDGE{int u,v;EDGE* ne;
}edge[1000010];struct NODE{EDGE* fir;
}node[1000010];int tot;
void my_build(int u,int v){edge[tot].u=u;edge[tot].v=v;edge[tot].ne=node[u].fir;node[u].fir=&edge[tot];tot++;
}int dep[100010][20],ce[1000010];
void dfs(int u,int fa){ce[u]=ce[fa]+1;EDGE* i=node[u].fir;dep[u][0]=fa;for(int j=1;j<20;j++){dep[u][j]=dep[dep[u][j-1]][j-1];}while(i!=NULL){if(i->v==fa){i=i->ne;continue;}dfs(i->v,u);i=i->ne;}
}int lca(int u,int v){if(ce[u]<ce[v]){swap(u,v);}for(int i=19;i>=0;i--){if(ce[dep[u][i]]>=ce[v]){u=dep[u][i];}}if(u==v)return u;for(int i=19;i>=0;i--){if(dep[u][i]!=dep[v][i]){u=dep[u][i];v=dep[v][i];}}return dep[u][0];
}int sum[1000010];
void my_add(int u,int fa){EDGE* i=node[u].fir;while(i!=NULL){if(i->v==fa){i=i->ne;continue;}my_add(i->v,u);//注意不是dfs（找了很久的bug...）sum[u]+=sum[i->v];i=i->ne;}
}signed main()
{cin>>n>>m;int u,v;for(int i=1;i<=n-1;i++){cin>>u>>v;my_build(u,v);my_build(v,u);}dfs(1,0);for(int i=1;i<=m;i++){cin>>u>>v;int l=lca(u,v);sum[u]++;sum[v]++;sum[l]-=2;}my_add(1,0);int ans=0;for(int i=2;i<=n;i++){if(sum[i]==0){ans+=m;//注意是+m！！！}else if(sum[i]==1){ans++;}}cout<<ans;return 0;
}