@codechef - MXMN@ Maximum and Minimum

男娘i 2023-06-01 13:56 8阅读 0赞

*  @description@
 *  @solution@
 *  @accepted code@
 *  @details@

--------------------

## @description@ ##

定义函数 f(G, x, y) 为 G 中点 x 和点 y 之间的所有路径的权重（该路径上各边权的最大值）的最小值，其中 G 为一个有边权的无向连通图。  
给定两个 N 个点 M 条边连通图 G1 和 G2。请你计算：  
\\\[S = \\sum\_\{i=1\}^\{N-1\}\\sum\_\{j=i+1\}^\{B\}f(G1, i, j)\*f(G2, i, j) \\mod 998244353\\\]

**输入格式**  
输入的第一行包含两个整数 N 和 M。  
接下来的 M 行每行包含三个整数 u，v 和 w，表示 G1 中的点 u 和 v 由一条权重为 w 的边连接。  
再接下来的 M 行每行包含三个整数 u，v 和 w，表示 G2 中的点 u 和 v 由一条权重为 w 的边连接。

**输出格式**  
对于每组数据，输出一行包含一个整数，表示 S 对 998244353 取模的结果。

**数据范围**   
• 1 ≤ N ≤ 10^5  
• M = 2N  
• 1 ≤ u,v ≤ N  
• 1 ≤ w ≤ 10^8  
• G1 和 G2 都是连通图

**样例数据**  
**输入**  
3 6  
1 2 3  
2 3 1  
3 1 2  
1 2 4  
2 3 5  
3 1 6  
1 2 2  
2 3 1  
3 1 3  
1 2 5  
2 3 4  
3 1 6  
**输出**  
9

## @solution@ ##

考虑先分别建出两个图 G1、G2 的 kruskal 重构树 T1、T2，则问题变为：  
\\\[S = \\sum\_\{i=1\}^\{N-1\}\\sum\_\{j=i+1\}^\{N\}T1.key(T2.lca(i, j))\*T2.key(T2.lca(i, j))\\\]

求两棵树 lca 的权值乘积的和实际上是边分树合并的经典套路。  
我们考虑一遍边分治（因为 kruskal 重构树本身是二叉树，所以不用重构）建出边分树，左儿子存储中心边深度较小的那边连通块，右儿子存储中心边深度较大的那边连通块。  
于是跨越中心边 (m1, m2) 的路径 (u, v) 的 lca 只跟深度较小的那块连通块有关，不妨记 u 是深度较小的，则 lca(u, v) = lca(u, m1)。不妨将 u 对应的 T1.key(lca(u, m1)) 存储下来记作 f\[u\]。

枚举 T2.lca(i, j) 为 p 算出对应的 T1.key 之和。考虑将 p 的左右儿子的边分树合并得到 p 的边分树，同时统计答案。  
考虑在边分树上维护深度较小那边所有点 f 之和 sum，维护深度较大那边点的数量 cnt。则合并时用两棵边分树的 sum 和 cnt 两两相乘求和就是我们想要得到的东西。

## @accepted code@ ##

#include<cstdio> #include<algorithm> using namespace std; const int MAXN = 200000; const int MOD = 998244353; int lg[2*MAXN + 5]; struct Graph{ struct edge{ int to; bool tag; edge *nxt, *rev; }edges[2*MAXN + 5], *adj[MAXN + 5], *ecnt; Graph() {ecnt = &edges[0];} void addedge(int u, int v) { edge *p = (++ecnt), *q = (++ecnt); p->to = v, p->nxt = adj[u], adj[u] = p, p->tag = false; q->to = u, q->nxt = adj[v], adj[v] = q, q->tag = false; p->rev = q, q->rev = p; } int dep[MAXN + 5], dfn[2*MAXN + 5], fir[MAXN + 5], dcnt; void dfs(int x, int f) { dep[x] = dep[f] + 1, dfn[++dcnt] = x, fir[x] = dcnt; for(edge *p=adj[x];p;p=p->nxt) { if( p->to == f ) continue; dfs(p->to, x), dfn[++dcnt] = x; } } int st[20][2*MAXN + 5]; void get_st() { for(int i=1;i<=dcnt;i++) st[0][i] = dfn[i]; for(int j=1;j<20;j++) { int t = 1<<(j-1); for(int i=1;i+t<=dcnt;i++) st[j][i] = (dep[st[j-1][i]] < dep[st[j-1][i+t]]) ? st[j-1][i] : st[j-1][i+t]; } } void build(int x) {dcnt = 0; dfs(x, 0); get_st();} int lca(int x, int y) { if( fir[x] > fir[y] ) swap(x, y); x = fir[x], y = fir[y]; int k = lg[y-x+1], l = (1<<k); return (dep[st[k][x]] < dep[st[k][y-l+1]]) ? st[k][x] : st[k][y-l+1]; } }G1, G2; int siz[MAXN + 5]; bool cmp(Graph::edge *a, Graph::edge *b, int tot) { if( a == NULL ) return false; if( b == NULL ) return true; return max(siz[a->to], tot-siz[a->to]) < max(siz[b->to], tot-siz[b->to]); } Graph::edge *get_mid(int x, int f, int tot) { Graph::edge *ret = NULL; siz[x] = 1; for(Graph::edge *p=G1.adj[x];p;p=p->nxt) { if( p->tag || p->to == f ) continue; Graph::edge *tmp = get_mid(p->to, x, tot); siz[x] += siz[p->to]; if( cmp(tmp, ret, tot) ) ret = tmp; if( cmp(p, ret, tot) ) ret = p; } return ret; } int ch[2][MAXN + 5], etot = 0; bool dir[32][MAXN + 5]; int key[32][MAXN + 5]; int a[MAXN + 5], b[MAXN + 5], N, M; void dfs(const int &k, int x, int f, bool t, const int &dep) { dir[dep][x] = t; if( !t ) key[dep][x] = a[G1.lca(k, x)]; for(Graph::edge *p=G1.adj[x];p;p=p->nxt) { if( p->tag || p->to == f ) continue; dfs(k, p->to, x, t, dep); } } int divide(int x, int tot, int dep) { Graph::edge *m = get_mid(x, 0, tot); if( m == NULL ) return -1; m->tag = m->rev->tag = true; int tmp = (++etot); dfs(m->to, m->to, 0, G1.dep[m->to]>G1.dep[m->rev->to], dep); dfs(m->rev->to, m->rev->to, 0, G1.dep[m->to]<G1.dep[m->rev->to], dep); ch[G1.dep[m->to]>G1.dep[m->rev->to]][tmp] = divide(m->to, siz[m->to], dep + 1); ch[G1.dep[m->to]<G1.dep[m->rev->to]][tmp] = divide(m->rev->to, tot-siz[m->to], dep + 1); return tmp; } struct edge{ int u, v, w; friend bool operator < (edge a, edge b) { return a.w < b.w; } }e[MAXN + 5]; int fa[MAXN + 5]; int find(int x) { return fa[x] = (fa[x] == x) ? x : find(fa[x]) ; } struct node{ node *ch[2]; int cnt, sum; }nd[32*MAXN + 5], *rt[MAXN + 5], *ncnt, *NIL; node *new_tree(int nw, int x, int dep) { if( nw == -1 ) return NIL; node *p = (++ncnt); if( !dir[dep][x] ) p->sum = (p->sum + key[dep][x])%MOD; else p->cnt = (p->cnt + 1)%MOD; p->ch[dir[dep][x]] = new_tree(ch[dir[dep][x]][nw], x, dep + 1); p->ch[!dir[dep][x]] = NIL; return p; } int ans = 0, res = 0; node *merge(node *rt1, node *rt2) { if( rt1 == NIL ) return rt2; if( rt2 == NIL ) return rt1; res = (res + 1LL*rt1->cnt*rt2->sum%MOD) % MOD; res = (res + 1LL*rt1->sum*rt2->cnt%MOD) % MOD; rt1->sum = (rt1->sum + rt2->sum)%MOD; rt1->cnt = (rt1->cnt + rt2->cnt)%MOD; rt1->ch[0] = merge(rt1->ch[0], rt2->ch[0]); rt1->ch[1] = merge(rt1->ch[1], rt2->ch[1]); return rt1; } void dfs2(int x, int f) { if( x <= N ) rt[x] = new_tree(1, x, 0); else rt[x] = NIL; for(Graph::edge *p=G2.adj[x];p;p=p->nxt) { if( p->to == f ) continue; dfs2(p->to, x); } res = 0; for(Graph::edge *p=G2.adj[x];p;p=p->nxt) { if( p->to == f ) continue; rt[x] = merge(rt[x], rt[p->to]); } ans = (ans + 1LL*res*b[x]%MOD)%MOD; } void init() { for(int i=2;i<=2*MAXN;i++) lg[i] = lg[i>>1] + 1; ncnt = NIL = &nd[0]; NIL->ch[0] = NIL->ch[1] = NIL; NIL->cnt = NIL->sum = 0; } int main() { init(); scanf("%d%d", &N, &M); for(int i=1;i<=M;i++) scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w); sort(e + 1, e + M + 1); for(int i=1;i<=N;i++) fa[i] = i; int cnt = N; for(int i=1;i<=M;i++) { int fu = find(e[i].u), fv = find(e[i].v); if( fu != fv ) { a[++cnt] = e[i].w; fa[cnt] = cnt; fa[fu] = fa[fv] = cnt; G1.addedge(cnt, fu), G1.addedge(cnt, fv); } } G1.build(find(1)); divide(1, cnt, 0); for(int i=1;i<=M;i++) scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w); sort(e + 1, e + M + 1); for(int i=1;i<=N;i++) fa[i] = i; cnt = N; for(int i=1;i<=M;i++) { int fu = find(e[i].u), fv = find(e[i].v); if( fu != fv ) { b[++cnt] = e[i].w; fa[fu] = fa[fv] = fa[cnt] = cnt; G2.addedge(cnt, fu), G2.addedge(cnt, fv); } } dfs2(find(1), 0); printf("%d\n", ans); }

## @details@ ##

求 lca 时写了个 st 表求 rmq，然而 st 表需要二倍长度，然而我用的是一倍长度。。。

转载于:https://www.cnblogs.com/Tiw-Air-OAO/p/11335060.html