\(\mathcal{Description}\)

给定一个 \(n\) 个点 \(m\) 条边的连通无向图，并给出 \(q\) 个点对 \((u,v)\)，令 \(u\) 到 \(v\) 的路径所必经的结点权值 \(+1\)。求最终每个结点的权值。

\(n\le10^5\)，\(m,q\le2\times10^5\)。

\(\mathcal{Solution}\)

看到”必经之点“，应该考虑圆方树。

对于每个点对，直接在圆方树上作差分。具体地，两个圆点的 tag++，其 LCA 和 LCA 的父亲（如果存在）的 tag--，最后一遍 DFS 求每个圆点的子树 tag 和即可。

复杂度 \(\mathcal O(n)\)。

\(\mathcal{Code}\)

#include <cstdio>

const int MAXN = 1e5, MAXM = 2e5;

int n, m, q, snode;

int dfc, top, dfn[MAXN + 5], low[MAXN + 5], stk[MAXN + 5];

int dep[MAXN * 2 + 5], fa[MAXN * 2 + 5][20], tag[MAXN * 2 + 5], sum[MAXN * 2 + 5];

struct Graph {

	int ecnt, head[MAXN * 2 + 5], to[MAXM * 2 + 5], nxt[MAXM * 2 + 5];

	inline void link ( const int s, const int t ) {

		to[++ ecnt] = t, nxt[ecnt] = head[s];

		head[s] = ecnt;

	}

	inline void add ( const int u, const int v ) {

		link ( u, v ), link ( v, u );

	}

} src, tre;

inline bool chkmin ( int& a, const int b ) { return b < a ? a = b, true : false; }

inline void Tarjan ( const int u, const int f ) {

	dfn[u] = low[u] = ++ dfc, stk[++ top] = u;

	for ( int i = src.head[u], v; i; i = src.nxt[i] ) {

		if ( ( v = src.to[i] ) == f ) continue;

		if ( ! dfn[v] ) {

			Tarjan ( v, u ), chkmin ( low[u], low[v] );

			if ( low[v] >= dfn[u] ) {

				tre.add ( u, ++ snode );

				do tre.add ( snode, stk[top] ); while ( stk[top --] ^ v );

			}

		} else chkmin ( low[u], dfn[v] );

	}

}

inline void init ( const int u, const int f ) {

	dep[u] = dep[fa[u][0] = f] + 1;

	for ( int i = 1; i <= 17; ++ i ) fa[u][i] = fa[fa[u][i - 1]][i - 1];

	for ( int i = tre.head[u], v; i; i = tre.nxt[i] ) {

		if ( ( v = tre.to[i] ) ^ f ) {

			init ( v, u );

		}

	}

}

inline int calcLCA ( int u, int v ) {

	if ( dep[u] < dep[v] ) u ^= v ^= u ^= v;

	for ( int i = 17; ~ i; -- i ) if ( dep[fa[u][i]] >= dep[v] ) u = fa[u][i];

	if ( u == v ) return u;

	for ( int i = 17; ~ i; -- i ) if ( fa[u][i] ^ fa[v][i] ) u = fa[u][i], v = fa[v][i];

	return fa[u][0];

}

inline void calcAns ( const int u, const int f ) {

	sum[u] = tag[u];

	for ( int i = tre.head[u], v; i; i = tre.nxt[i] ) {

		if ( ( v = tre.to[i] ) ^ f ) {

			calcAns ( v, u ), sum[u] += sum[v];

		}

	}

}

int main () {

	scanf ( "%d %d %d", &n, &m, &q ), snode = n;

	for ( int i = 1, u, v; i <= m; ++ i ) {

		scanf ( "%d %d", &u, &v );

		src.add ( u, v );

	}

	Tarjan ( 1, 0 ), init ( 1, 0 );

	for ( int i = 1, u, v; i <= q; ++ i ) {

		scanf ( "%d %d", &u, &v );

		++ tag[u], ++ tag[v];

		int w = calcLCA ( u, v );

		-- tag[w];

		if ( fa[w] ) -- tag[fa[w][0]];

	}

	calcAns ( 1, 0 );

	for ( int i = 1; i <= n; ++ i ) printf ( "%d\n", sum[i] );

	return 0;

}

巴特西

Solution -「BZOJ 3331」压力

\(\mathcal{Description}\)

\(\mathcal{Solution}\)

\(\mathcal{Code}\)

最新文章

热门文章