注视一切的终结

本文主要是介绍注视一切的终结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

注视一切的终结

题目大意

给出一个 $n$ 个点 $m$ 条边的图，每条边有一个颜色 $w_i$ 。保证这个图删除了所有重边后变成一棵树

一条路径的权值就是相邻的两条边的 $w_i$ 值不相同的个数

有 $Q$ 次询问，每次询问给出两个点 $x,y$ ，求 $x$ 到 $y$ 的所有简单路径的权值的最大值

简单路径：路径上的所有顶点不重复。

思路

倍增、 $dp$

显然，对于两个点之间的边，我们只用维护至多 $3$ 种不同颜色的就可以了

设 $d{p}_{x,i,a,b}$ 表示一条 $x$ 到距离它的 $2^i$ 距离的祖先的一条路径，靠近 $x$ 的那一端的颜色是 $a$ ，$x$ 的 $2^i$ 级祖先上面的那条边是 $b$ 的路径的最大权值。

那么
$$f_{x,0,a,b}=(co{l}_a\ne co{l}_b)$$
转移是枚举 $x,y=f{a}_{x,i-1},z=f{a}_{x,i}$ ，颜色分别设为 $a,b,c$ ，则转移为 f x , i , a , b = max ⁡ { f x , i − 1 , a , b + f y , i − 1 , b , c } f_{x , i , a , b} = \max\{f_{x , i - 1 , a , b} + f_{y , i - 1 , b , c}\} fx,i,a,b​=max{fx,i−1,a,b​+fy,i−1,b,c​}

对于每个询问 $x,y$

设他们的 $lca$ 的儿子节点分别是 $fx,fy$ ，分别求出 $c{x}_i,c{y}_j$ 表示 $fx,fy$ 到 $lca$ 的所有不同颜色的边的最大权值。

若其中一个点是 $lca$ ，那么答案就是另一个点的最大值，否则再枚举一遍 $lca$ 下两条边的颜色 a n s = max ⁡ { c x a + c y b + ( c o l a ≠ c o l b ) } ans = \max\{cx_a +cy_b + (col_a \neq col_b)\} ans=max{cxa​+cyb​+(cola​=colb​)}

代码超级难调

code

#include <bits/stdc++.h>
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)
#define fd(x , y , z) for(int x = y ; x >= z ; x --)
using namespace std;
const int N = 5e5 + 5 , M = 1e6 + 5;
int ecnt , hd[N] , fa[N][21] , dep[N] , vis[N] , cnt[N] , col[N][4] , f[N][21][4][4] , n , m;
struct E {int to , nt , w;
} e[M << 1];
void add (int x , int y , int z) { e[++ecnt].to = y , e[ecnt].w = z , e[ecnt].nt = hd[x] , hd[x] = ecnt; }
int Lca (int x , int y) {if (dep[x] < dep[y]) swap (x , y);fd (i , 20 , 0) if (dep[fa[x][i]] >= dep[y])x = fa[x][i];if (x == y) return x;fd (i , 20 , 0) if (fa[x][i] != fa[y][i])x = fa[x][i] , y = fa[y][i];return fa[x][0];
}
void dfs1 (int x) {vis[x] = 1;fu (i , 1 , 20) fa[x][i] = fa[fa[x][i - 1]][i - 1];int y;for (int i = hd[x] ; i ; i = e[i].nt) {y = e[i].to;if (y == fa[x][0]) {if (cnt[x] == 3) continue;int flg = 0;fu (j , 1 , cnt[x]) if (col[x][j] == e[i].w) {flg = 1;break;}if (flg) continue;col[x][++cnt[x]] = e[i].w;}if (vis[y]) continue;dep[y] = dep[x] + 1;fa[y][0] = x;dfs1 (y);}
}
void dfs2 (int x) {vis[x] = 1;int y;if (x != 1) {y = fa[x][0];fu (j , 1 , cnt[x]) fu (k , 1 , cnt[fa[x][0]])f[x][0][j][k] = (col[x][j] != col[fa[x][0]][k]); }int z;for(int i=1;(1<<i)<=dep[x];i++) {y = fa[x][i - 1] , z = fa[x][i];fu (a , 1 , cnt[x]) {fu (b , 1 , cnt[y]) {fu (c , 1 , cnt[z]) {f[x][i][a][c] = max (f[x][i][a][c] , f[x][i - 1][a][b] + f[y][i - 1][b][c]);}}}}for (int i = hd[x] ; i ; i = e[i].nt) {y = e[i].to;if (vis[y]) continue;dfs2 (y);}
}
int jump (int x , int d , int c[]) {int cc[5] , y;fd (i , 20 , 0) {if (dep[fa[x][i]] > d) {y = fa[x][i];memset (cc , 0 , sizeof (cc));fu (a , 1 , cnt[x])fu (b , 1 , cnt[y])cc[b] = max (cc[b] , c[a] + f[x][i][a][b]);x = fa[x][i];memcpy (c , cc , sizeof (cc));}}return x;
}
int main () { // freopen ("a.in" , "r" , stdin);// freopen ("c.out" , "w" , stdout);int u , v , w;scanf ("%d%d" , &n , &m);fu (i , 1 , m) {scanf ("%d%d%d" , &u , &v , &w);add (u , v , w) , add (v , u , w);}dep[1] = 1;dfs1 (1);fu (i , 1 , n) vis[i] = 0;dfs2 (1);int T , x , y , lca , fx , fy , cx[5] , cy[5] , ans;scanf ("%d" , &T);int ans1 =  0;while (T --) {memset (cx , 0 , sizeof (cx)) , memset (cy , 0 , sizeof (cy));fx = fy = 0;scanf ("%d%d" , &x , &y);lca = Lca (x , y);if (x != lca) fx = jump (x , dep[lca] , cx);if (y != lca) fy = jump (y , dep[lca] , cy);ans = 0;if (x == lca)fu (i , 1 , cnt[fy]) ans = max (ans , cy[i]);else if (y == lca) fu (i , 1 , cnt[fx])ans = max (ans , cx[i]);else {fu (i , 1 , cnt[fx]) {fu (j , 1 , cnt[fy]) {ans = max (ans , cx[i] + cy[j] + (col[fx][i] != col[fy][j]));}}} printf ("%d\n" , ans);}return 0;
}

这篇关于注视一切的终结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---