我是这样做网站的米课,四年级说新闻2023,合肥地区建网站公司,微网站内容页模板前言#xff1a;
题目链接#xff1a;P3128 [USACO15DEC] Max Flow P - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
讲解#xff1a;
这一题含金量真算高的#xff0c;包含了建树#xff08;用了图论的知识#xff09;#xff0c;求最近公共祖先#xff08;倍增法…前言
题目链接P3128 [USACO15DEC] Max Flow P - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
讲解
这一题含金量真算高的包含了建树用了图论的知识求最近公共祖先倍增法还有树上差分第一次听树上还有差分吧
这些知识有欠缺的去学习一下上面的几个小知识点吧 思路
该题我一开始的思路是虽然一个父亲有多个孩子但是孩子只有一个父亲就准备用一个fa数组或者一个map(孩子是键值)来存父子关系然后有一个book数组当输入s和t时就从t加到s用book标记每个点的经过次数后面发现这个做法不可行-----原因1给出的x和y并不确定哪个是父亲 原因2s和t也不确定哪个是父亲-------思路转变 该题实际要第四声求的是被经过最多次数的点这个题涉及到的是图或者树并且更改的是一段中的数据-------频繁更改某个区间-------想到差分-----树差分 当涉及更改某个区间时我想到了线段树但是线段树一般方便查询的是 某个区间 的相关属性如区间和但是该题最后并未涉及和区间有关的求值而是求单点的信息因此线段树这种做法可以放后面考虑 但是线段树是可以做的也有相关的题解感兴趣的和想复习线段树的大佬可以去做做 AC代码
const int N 5e4 5;
const int M N - 1;int cnt;
int head[N];
int fa[N][21];
int deepth[N];
int power[N];
int ans;struct EDGE
{int v;int next;
}EDGE[M * 2];void add(int u, int v)
{cnt;EDGE[cnt].v v;EDGE[cnt].next head[u];head[u] cnt;
}void dfs(int son, int father)
{//第2^0个父亲就是这个父亲fa[son][0] father;//儿子深度 父亲深度 1deepth[son] deepth[father] 1;//算低2 ^ i个父亲是谁for (int i 1; (1 i)/*注意不是i 1*/ deepth[son]; i)fa[son][i] fa[fa[son][i - 1]][i -1];//公式for (int i head[son]; i; i EDGE[i].next){int v EDGE[i].v;if (v ! father)/**/dfs(v, son);}
}int lca(int x, int y)
{if (deepth[x] deepth[y])//要让x在y下面这样子方便后面统一处理swap(x, y);//使得x,y位于同一高度for (int i 20; i 0; i--)//注意是逆序原因:1、从上往下找比较快 2、若为顺序则越往上走找的父亲跨度越大不符合要求{if (deepth[fa[x][i]] deepth[y])x fa[x][i];}if (x y)//如果两个点已经重合return x;//找公共祖先且使得x,y位于公共祖先的下一层for (int i 20; i 0; i--){if (fa[x][i] ! fa[y][i]){x fa[x][i];y fa[y][i];}}return fa[x][0];//因为位于公共祖先的下一层所以他们的父亲就是公共祖先
}void getans(int son, int father)
{for (int i head[son]; i; i EDGE[i].next){if (EDGE[i].v father)/**/continue;getans(EDGE[i].v, son);power[son] power[EDGE[i].v];}ans max(ans, power[son]);
}void solve()
{int n, k;cin n k;int u, v, w;//建树for (int i 0; i n - 1; i){cin u v;add(u, v);add(v, u);}dfs(1, 0);//求第2 ^ n个父亲//求公共祖先、树上差分for (int i 0; i k; i){cin u v;int togetherfather lca(u, v);power[u];power[v];power[togetherfather]--;power[fa[togetherfather][0]]--;}getans(1, 0);cout ans endl;
}int main()
{solve();return 0;
}
