素马杭州网站设计介绍,船员专用网站开发建议,单页手机网站源码,餐饮平台app有哪些//** 太久不写了#xff0c;感觉很难受。。。比赛最近打得也不好#xff0c;课内任务又重#xff0c;还要忙着做项目。何去何从。
今天又写了一题#xff0c;用了树上差分的知识。下面来整理整理。 1.首先让我们学一下lca#xff08;最小公共父节点#xff09;
我用的…//** 太久不写了感觉很难受。。。比赛最近打得也不好课内任务又重还要忙着做项目。何去何从。
今天又写了一题用了树上差分的知识。下面来整理整理。 1.首先让我们学一下lca最小公共父节点
我用的是倍增来求的。总共其实就是两步dfs打ST表预处理每个点的上面节点 lca求两点最小公共节点。lca里用了类似dp的思想。首先要知道dep[i][j]表示 i点向上跳1j个点后到达的点。然后想出递推关系式dep[i][j]dep[dep[i][j-1]][j-1]。用dfs来递推实现即可。
lca的实现其实就是 1.先将两个点化为同一层的点 2.寻找那一层的父节点是一样的
下面来看一下代码~
//倍增法求最近公共祖先LCA
#includeiostream
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].uu;edge[tot].vv;edge[tot].ll;edge[tot].nenode[u].fir;node[u].firedge[tot];tot;
}int ce[100010],dep[100010][20];//ce表示每个点的层数 dep[i][j]表示从第i个点向上走 1j (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 i1;i19;i){dep[u][i]dep[dep[u][i-1]][i-1];//类似dp}EDGE* inode[u].fir;while(i!NULL){if(i-vf){ii-ne;continue;}dfs(i-v,u);ii-ne;}
}int lca(int u,int v){ //LCA 复杂度lognif(ce[u]ce[v]){swap(u,v);}for(int i19;i0;i--){if(ce[dep[u][i]]ce[v]){udep[u][i];}}if(uv)return u;for(int i19;i0;i--){if(dep[u][i]!dep[v][i]){udep[u][i];vdep[v][i];}}return dep[u][0];
}int main()
{cinnm;//建边之类...略return 0;
}2.树上差分
树上差分分两种1.给点差分 2.给边差分
对应着两种不一样的题意给点操作还是给边操作。
给点操作很好理解就是每个点加加减减。但如果要给边操作我们无法轻松表示边呐so我们就以点代边每个点表示其与父节点连接的边。
看一下操纵吧~
//给每个点做差分例如 给u-v路径上所有点1sum[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* inode[u].fir;while(i!NULL){if(i-vfa){ii-ne;continue;}dfs(i-v,u);sum[u]sum[i-v];ii-ne;}
}//差分数组(以给边差分为例)
while(m--){cinuv;int llca(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
4 1
1 2
2 3
1 4
3 4样例输出 Copy
3提示
对于20%的数据N≤100M≤100。 对于100%的数据N≤100000M≤200000。数据保证答案不超过231–1。 这题用的就是树上差分lca。而且是面向边的树上差分因为是要切边。
看代码~
#includeiostream
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].uu;edge[tot].vv;edge[tot].nenode[u].fir;node[u].firedge[tot];tot;
}int dep[100010][20],ce[1000010];
void dfs(int u,int fa){ce[u]ce[fa]1;EDGE* inode[u].fir;dep[u][0]fa;for(int j1;j20;j){dep[u][j]dep[dep[u][j-1]][j-1];}while(i!NULL){if(i-vfa){ii-ne;continue;}dfs(i-v,u);ii-ne;}
}int lca(int u,int v){if(ce[u]ce[v]){swap(u,v);}for(int i19;i0;i--){if(ce[dep[u][i]]ce[v]){udep[u][i];}}if(uv)return u;for(int i19;i0;i--){if(dep[u][i]!dep[v][i]){udep[u][i];vdep[v][i];}}return dep[u][0];
}int sum[1000010];
void my_add(int u,int fa){EDGE* inode[u].fir;while(i!NULL){if(i-vfa){ii-ne;continue;}my_add(i-v,u);//注意不是dfs找了很久的bug...sum[u]sum[i-v];ii-ne;}
}signed main()
{cinnm;int u,v;for(int i1;in-1;i){cinuv;my_build(u,v);my_build(v,u);}dfs(1,0);for(int i1;im;i){cinuv;int llca(u,v);sum[u];sum[v];sum[l]-2;}my_add(1,0);int ans0;for(int i2;in;i){if(sum[i]0){ansm;//注意是m}else if(sum[i]1){ans;}}coutans;return 0;
}
