压力[BJOI2013]

AK-dream

发布于：2020年7月31日

题目描述

如今,路由器和交换机构建起了互联网的骨架。处在互联网的骨干位置的核心路由器典型的要处理100Gbit/s的网络流量。他们每天都生活在巨大的压力之下。小强建立了一个模型。这世界上有$N$个网络设备,他们之间有$M$个双向的链接。这个世界是连通的。在一段时间里,有$Q$个数据包要从一个网络设备发送到另一个网络设备。一个网络设备承受的压力有多大呢?很显然,这取决于$Q$个数据包各自走的路径。不过,某些数据包无论走什么路径都不可避免的要通过某些网络设备。你要计算：对每个网络设备,必须通过(包括起点、终点)他的数据包有多少个?

输入格式

第一行包含3个由空格隔开的正整数$N,M,Q$。接下来$M$行,每行两个整数$u,v$,表示第$u$个网络设备(从$1$开始编号)和第$v$个网络设备之间有一个链接。$u$不会等于$v$。两个网络设备之间可能有多个链接。接下来$Q$行,每行两个整数$p,q$,表示第$p$个网络设备向第$q$个网络设备发送了一个数据包。$p$不会等于$q$。

输出格式

输出$N$行,每行$1$个整数,表示必须通过某个网络设备的数据包的数量。

题解

如果有一条路径必须经过某个点$x$，那么显然点$x$必为一个割点。

所以建出原图的圆方树，其中每个非叶子的圆点必然代表着原图的一个割点

然后对于一次$x$到$y$的数据传输，必须经过圆方树上$x,y$两点之间的路径，所以使用树上差分统计每个非叶子圆点被经过多少次即可

时间复杂度$O(n\log n)$

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

template<typename T>
inline void read(T &num) {
	T x = 0, f = 1; char ch = getchar();
	for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1;
	for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ '0');
	num = x * f;
}

int n, nn, m, Q;
int head[400005], pre[400005], to[400005], sz;

void addedge(int u, int v) {
	pre[++sz] = head[u]; head[u] = sz; to[sz] = v; 
	pre[++sz] = head[v]; head[v] = sz; to[sz] = u;
}

int dfn[400005], low[400005], tme, q[400005], top;
vector<int> e[400005];
int f[400005];

void tarjan(int x) {
	dfn[x] = low[x] = ++tme;
	q[++top] = x;
	int now = 0;
	for (int i = head[x]; i; i = pre[i]) {
		int y = to[i];
		if (!dfn[y]) {
			tarjan(y);
			low[x] = min(low[x], low[y]);
			if (dfn[x] <= low[y]) {
				n++;
				int z = 0;
				do {
					z = q[top];
					e[n].push_back(z);
					e[z].push_back(n);
					top--;
				} while (z != y);
				e[n].push_back(x);
				e[x].push_back(n);
			}
		} else {
			low[x] = min(low[x], dfn[y]);
		}
	}
}

int d[400005], p[400005][21];

void dfs1(int x, int fa) {
	for (int i = 0; i < e[x].size(); i++) {
		int y = e[x][i];
		if (y == fa) continue;
		d[y] = d[x] + 1;
		p[y][0] = x;
		dfs1(y, x);
	}
}

int LCA(int x, int y) {
	if (d[x] < d[y]) swap(x, y);
	for (int i = 20; i >= 0; i--) {
		if (d[x] - (1 << i) >= d[y]) x = p[x][i];
	}
	if (x == y) return x;
	for (int i = 20; i >= 0; i--) {
		if (p[x][i] != p[y][i]) {
			x = p[x][i]; y = p[y][i];
		}
	}
	return p[x][0];
}

void dfs(int x, int fa) {
	for (int i = 0; i < e[x].size(); i++) {
		int y = e[x][i];
		if (y == fa) continue;
		dfs(y, x);
		f[x] += f[y];
	}
}

int main() {
	read(n); nn = n; read(m); read(Q);
	for (int i = 1; i <= m; i++) {
		int a, b;
		read(a); read(b);
		addedge(a, b);
	}
	tarjan(1);
	dfs1(1, 0);
	for (int l = 1; (1 << l) <= n; l++) {
		for (int i = 1; i <= n; i++) {
			p[i][l] = p[p[i][l-1]][l-1];
		}
	}
	for (int i = 1; i <= Q; i++) {
		int x, y, lca;
		read(x); read(y);
		lca = LCA(x, y);
		f[x]++; f[y]++; f[lca]--; f[p[lca][0]]--;
	}
	dfs(1, 0);
	for (int i = 1; i <= nn; i++) {
		printf("%d\n", f[i]);
	}
	return 0;
}