jzoj5844 c 倍增
程序员文章站
2024-02-12 22:46:22
...
Description
给定一个无向连通图,n 个点(下标从 1 开始),m 条边,每条边有一个颜色。保证无自环,没有长度超过 2 的简单环。
现有 q 个询问:给出两个点 x、y,选择一条 x 到 y 简单路径(不经过重复的点),经过的边将形成一个颜色序列,价值为相同颜色的极大连续段个数,求出最大的价值。
Solution
人均3k码量,鸣谢LZH犇给的的对拍
一开始就看错题意了,以为是最长的颜色连续长度,然鹅是最多的段数
考虑树形图要怎么做。由于每一条树边唯一对应一个边权,直接倍增/树剖统计就行了
这非常有启发性。注意到一条链上的边最多与两条链相邻,因此我们只需要记录一条边上的三种不同权值。用r[x][i][s1][s2]表示从x出发向上2^i层后,最顶端和最底端两条边的权编号为s1、s2时的最大分段数
这道题口胡非常容易,写起来细节比较多(我比较菜
比如我们可以把边权下放给儿子,用down[x][i]记录x向上2^i层后链上倒数第二个节点,这样可以比较方便地求出顶端和底端的链的权
比如dfs的时候要考虑出现沿着很多个小环走成大环的情况
写出来很有成就感
Code
#include <stdio.h>
#include <string.h>
#include <vector>
#include <map>
#define rep(i,st,ed) for (int i=st;i<=ed;++i)
#define drp(i,st,ed) for (int i=st;i>=ed;--i)
#define copy(x,t) memcpy(x,t,sizeof(x))
#define fill(x,t) memset(x,t,sizeof(x))
const int N=300005;
const int E=600005;
std:: map <int,bool> map[N];
struct edge {int y,w,next;} e[E];
int fa[N][18],r[N][18][4][4],dep[N],down[N][18];
int wjp[4][4],tmp1[4][4],tmp2[4][4],ret[4][4],c[N][4];
int ls[N],edCnt;
bool vis[N];
int read() {
int x=0,v=1; char ch=getchar();
for (;ch<'0'||ch>'9';v=(ch=='-')?(-1):(v),ch=getchar());
for (;ch<='9'&&ch>='0';x=x*10+ch-'0',ch=getchar());
return x*v;
}
void add_edge(int x,int y,int w) {
e[++edCnt]=(edge) {y,w,ls[x]}; ls[x]=edCnt;
e[++edCnt]=(edge) {x,w,ls[y]}; ls[y]=edCnt;
}
void dfs1(int now) {
rep(i,1,17) fa[now][i]=fa[fa[now][i-1]][i-1];
rep(i,1,17) down[now][i]=down[fa[now][i-1]][i-1];
vis[now]=true;
for (int i=ls[now];i;i=e[i].next) {
if (vis[e[i].y]) continue;
dep[e[i].y]=dep[now]+1; fa[e[i].y][0]=now;
down[e[i].y][0]=e[i].y;
dfs1(e[i].y);
}
}
void work(int now) {
rep(i,1,17) {
rep(c1,1,c[now][0]) rep(c2,1,c[down[now][i-1]][0]) {
rep(c3,1,c[fa[now][i-1]][0]) rep(c4,1,c[down[now][i]][0]) {
r[now][i][c1][c4]=std:: max(r[now][i][c1][c4],r[now][i-1][c1][c2]+r[fa[now][i-1]][i-1][c3][c4]-(c[down[now][i-1]][c2]==c[fa[now][i-1]][c3]));
}
}
}
for (int i=ls[now];i;i=e[i].next) {
if (dep[e[i].y]<=dep[now]) continue;
if (c[e[i].y][0]==3) continue;
bool flag=true;
rep(j,1,c[e[i].y][0]) {
if (c[e[i].y][j]==e[i].w) {
flag=false; break;
}
}
if (flag) c[e[i].y][++c[e[i].y][0]]=e[i].w;
}
for (int i=ls[now];i;i=e[i].next) {
if (dep[e[i].y]<=dep[now]) continue;
rep(j,1,c[e[i].y][0]) {
r[e[i].y][0][j][j]=1;
}
}
}
void dfs2(int now) { vis[now]=true;
work(now);
for (int i=ls[now];i;i=e[i].next) {
if (vis[e[i].y]) continue;
dfs2(e[i].y);
}
}
int get_lca(int x,int y) {
if (dep[x]<dep[y]) std:: swap(x,y);
drp(i,17,0) if (dep[fa[x][i]]>=dep[y]) x=fa[x][i];
if (x==y) return x;
drp(i,17,0) if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
int get_up(int x,int up) {
fill(ret,0); int last=x,st=x;
bool first=true;
drp(i,17,0) {
if (dep[fa[x][i]]>=dep[up]) {
fill(wjp,0);
if (first) {
copy(wjp,r[x][i]);
first=false;
} else {
rep(c1,1,c[st][0]) rep(c2,1,c[last][0]) {
rep(c3,1,c[x][0]) rep(c4,1,c[down[x][i]][0]) {
wjp[c1][c4]=std:: max(wjp[c1][c4],ret[c1][c2]+r[x][i][c3][c4]-(c[last][c2]==c[x][c3]));
}
}
}
copy(ret,wjp); last=down[x][i]; x=fa[x][i];
}
}
return last;
}
void solve(int x,int y) {
int lca=get_lca(x,y),ans=0,ux,uy;
if (x==lca) {
uy=get_up(y,lca); copy(tmp2,ret);
rep(c1,1,c[y][0]) rep(c2,1,c[uy][0]) {
ans=std:: max(ans,tmp2[c1][c2]);
}
} else if (y==lca) {
ux=get_up(x,lca); copy(tmp1,ret);
rep(c1,1,c[x][0]) rep(c2,1,c[ux][0]) {
ans=std:: max(ans,tmp1[c1][c2]);
}
} else {
ux=get_up(x,lca); copy(tmp1,ret);
uy=get_up(y,lca); copy(tmp2,ret);
rep(c1,1,c[x][0]) rep(c2,1,c[ux][0]) {
rep(c3,1,c[y][0]) rep(c4,1,c[uy][0]) {
ans=std:: max(ans,tmp1[c1][c2]+tmp2[c3][c4]-(c[ux][c2]==c[uy][c4]));
}
}
}
printf("%d\n", ans);
}
int main(void) {
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
int n=read(),m=read();
rep(i,1,m) {
int x=read(),y=read(),w=read();
add_edge(x,y,w);
}
dep[1]=1; dfs1(1); fill(vis,0);
dfs2(1);
for (int T=read();T--;) {
int x=read(),y=read();
solve(x,y);
}
return 0;
}