烟台商机互联做网站吗,wordpress 扫码付费,品牌厂家网站建设,怎么样做长久的电影网站模板
1. Tarjan 一个讲的很好的视频#xff1a;D10 Tarjan算法 P3379【模板】最近公共祖先#xff08;LCA#xff09;_哔哩哔哩_bilibili#xff0c;董晓算法出品。
Tarjan总体来说可以概括为#xff1a;
记录访达#xff1a;记录某个节点是否已经访问过#xff0c;防…模板
1. Tarjan 一个讲的很好的视频D10 Tarjan算法 P3379【模板】最近公共祖先LCA_哔哩哔哩_bilibili董晓算法出品。
Tarjan总体来说可以概括为
记录访达记录某个节点是否已经访问过防环向下深搜深搜子节点回溯指父低层回溯时将子节点归于当前父节点所在等价类中离时查询本层向上回溯时查询与当前节点所有相关的LCA记录答案
package Tarjan.LCA;import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;public class TarjanLCA {private ListInteger[] e;private Listint[][] query;private int[] fa;private boolean[] vis;private int[] ans;/*** 求LCA* param edge 边集* param queries 查询* param n 总共几个节点* return 查询对应的LCA集合*/public int[] Tarjan(int[][] edge,int[][] queries,int n,int root){e new ArrayList[n];Arrays.setAll(e,e-new ArrayList());query new ArrayList[n];Arrays.setAll(query,e-new ArrayList());fa new int[n];for (int i 0; i fa.length; i) {fa[i] i;}vis new boolean[n];Arrays.fill(vis,false);ans new int[queries.length];// 邻接表建边for (int[] es : edge) {e[es[0]].add(es[1]);e[es[1]].add(es[0]);}// tarjan 查询数组for (int i 0; i queries.length; i) {int[] qs queries[i];query[qs[0]].add(new int[]{qs[1],i});query[qs[1]].add(new int[]{qs[0],i});}dfs(root);return ans;}private void dfs(int node){vis[node] true;for (Integer child : e[node]) {if(!vis[child]){dfs(child);fa[child] node;}}// 向上一层返回时记录LCAfor (int[] q : query[node]) {if(vis[q[0]]){ans[q[1]] find(q[0]);}}}private int find(int x){if(fa[x]!x){fa[x] find(fa[fa[x]]);}return fa[x];}}这里有几个要注意的地方
查询数组记得要对称设置比如查34的lca3要放1个4也要放1个。因为到底哪个先深搜到是不确定的。比如就放了3的那如果先深搜到3发现此时4压根就没指父过压根没访问到这个查询对应的答案就没法记录了。所以都放一个绝对可以防止深搜顺序的不确定性。并查集的路径压缩并不会影响查询结果。因为是回溯时查询所以绝对是从低层起的随着逐渐往根处的回溯并查集中等价类会逐渐向根扩张并以根为祖宗节点。
这里放一个例子可以对照代码手玩一下 0/ \4 3/|\ \1 5 6 8/ \2 7测试用例可自选。
1. LC 2846 边权重均等查询
树的定义是连通无回路的图所以会有以下性质
任意两个节点间有且仅有一条通路任意节点至多有一个父节点
所以要查询任意两个节点之间的最小操作次数可以唯一地确定答案。因为这两个节点之间存在且仅只存在一条通路。
这个贪心其实很显然就是对于一条链让其他权重向频率最大的那个靠近即可。比如这条链上的权重为
[ 1 , 1 , 2 , 2 , 2 , 3 ]很显然答案是把1和3全部变成2操作次数是3。
那么怎么计算这条链上的操作次数呢这里定义i→j为从节点i到节点j上的链上各权重出现频次。计算公式为
op(i-j) ∑(op(0-i) op(0-j) - 2*op(0-lca(i,j)))
其中lca表示最近公共祖先举个例子 0/ \4 3/|\ \1 5 6 8/ \2 7假设我们要看6→7这条链那么可以计算 0→6 0→7 - 0→4 - 0→4的各权重出现频次。因为0→4多算了两次那么这个公式是否具有普适性呢假设现在要看4→3这条链可以计算0→40→3 - 2* 0→0也是适用的。
所以思路就是我们先通过深搜求出来每个节点到根节点一颗无向树谁都可以作为根节点不妨设为00的链上各权重出现频次。然后利用tarjan求出来每组查询的公共祖先带入上述公式计算即可。
深搜求频次的思路是由于本层递归比上一层就多了一个上一层节点到本层节点的权重因此我们可以复制上一层节点本层节点的父节点的各权重频次再在当前权重上增1即可。
而利用性质2可以简单的记录fa节点判环。但tarjan是不能这样做的因为需要明确离时查询时另一个节点是否已经访问并不只是简单的判环功能。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;class Solution {Listint[][] e;Listint[][] qs;int[][] cnt;int[] lca;int[] fa;boolean[] vis;int[] ans;public int[] minOperationsQueries(int n, int[][] edges, int[][] queries) {e new ArrayList[n];qs new ArrayList[n];Arrays.setAll(e,e-new ArrayList());Arrays.setAll(qs,e-new ArrayList());int u,v,w;//邻接表for (int[] edge : edges) {u edge[0];v edge[1];w edge[2];e[u].add(new int[]{v,w});e[v].add(new int[]{u,w});}// tarjan 查询for (int i 0; i queries.length; i) {int[] q queries[i];qs[q[0]].add(new int[]{q[1],i});qs[q[1]].add(new int[]{q[0],i});}cnt new int[n][26];cnt_dfs(0,-1,0);lca new int[queries.length];fa new int[n];for (int i 0; i fa.length; i) {fa[i] i;}vis new boolean[n];Arrays.fill(vis,false);tarjan(0);ans new int[queries.length];calAns(queries);return ans;}private void cnt_dfs(int node,int father,int weight){if(father!-1){cnt[node] Arrays.copyOf(cnt[father],26);cnt[node][weight-1];}for (int[] child : e[node]) {if(child[0]!father){cnt_dfs(child[0],node,child[1]);}}}private void tarjan(int node){vis[node] true;for (int[] child : e[node]) {if(!vis[child[0]]){tarjan(child[0]);// tarjan 回溯指父fa[child[0]] node;}}// 离时查询for (int[] q : qs[node]) {if(vis[q[0]]){lca[q[1]] find(q[0]);}}}private int find(int x){if(fa[x]!x){fa[x] find(fa[fa[x]]);}return fa[x];}private void calAns(int[][] queries){int sum,max;for (int index 0; index queries.length; index) {sum 0;max Integer.MIN_VALUE;int u queries[index][0];int v queries[index][1];for(int i0;i26;i){int freq cnt[u][i] cnt[v][i] - 2*cnt[lca[index]][i];sum freq;max Math.max(freq,max);}ans[index] sum-max;}}}
