注视一切的终结
文章目录
- 注视一切的终结
-
- 题目大意
- 思路
- code
题目大意
给出一个
n
n
n 个点
m
m
m 条边的图，每条边有一个颜色
w
i
w_i
wi 。保证这个图删除了所有重边后变成一棵树
一条路径的权值就是相邻的两条边的
w
i
w_i
wi 值不相同的个数
有
Q
Q
Q 次询问，每次询问给出两个点
x
,
y
x , y
x,y ，求
x
x
x 到
y
y
y 的所有简单路径的权值的最大值
简单路径：路径上的所有顶点不重复。
思路
倍增、
d
p
dp
dp
显然，对于两个点之间的边，我们只用维护至多
3
3
3 种不同颜色的就可以了
设
d
p
x
,
i
,
a
,
b
dp_{x , i , a , b}
dpx,i,a,b 表示一条
x
x
x 到距离它的
2
i
2^i
2i 距离的祖先的一条路径，靠近
x
x
x 的那一端的颜色是
a
a
a ，
x
x
x 的
2
i
2 ^ i
2i 级祖先上面的那条边是
b
b
b 的路径的最大权值。
那么
f
x
,
0
,
a
,
b
=
(
c
o
l
a
≠
c
o
l
b
)
f_{x , 0 , a , b} = (col_a neq col_b)
fx,0,a,b=(cola=colb)
转移是枚举
x
,
y
=
f
a
x
,
i
−
1
,
z
=
f
a
x
,
i
x,y = fa_{x , i – 1} , z = fa_{x , i}
x,y=fax,i−1,z=fax,i ，颜色分别设为
a
,
b
,
c
a , b , c
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
x , y
x,y
设他们的
l
c
a
lca
lca 的儿子节点分别是
f
x
,
f
y
fx , fy
fx,fy ，分别求出
c
x
i
,
c
y
j
cx_i , cy_j
cxi,cyj 表示
f
x
,
f
y
fx , fy
fx,fy 到
l
c
a
lca
lca 的所有不同颜色的边的最大权值。
若其中一个点是
l
c
a
lca
lca ，那么答案就是另一个点的最大值，否则再枚举一遍
l
c
a
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
#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;(1i)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 ("%dn" , ans);
}
return 0;
}
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
数据类型 在第一个程序中，有这样一条语句：int main（）{}，此时，我们已经知道这是C语言中不可缺少的主函数。我们也了解到了int是最常见的一种数据类型，那么它叫什么名字呢？下面我们就来认识一些常用的数据类型。 char——>字符型(像”a”、”b…
