题面
3. 树多
题目ID：19177必做题文件操作100分
最新提交：
Wrong Answer
0 分
历史最高：
Runtime Error
15 分
时间限制: 4000ms
空间限制: 262144kB
输入文件名: seert.in
输出文件名: seert.out
题目描述
给定 n,kn,k 和 kk 棵有 nn 个点的树。对于每个点对 (i,j)(i,j)，求出其在每棵树上的路径经过的点（含端点）的并集大小。
输入格式
从文件 seert.in 中读入数据。
第一行两个正整数 n,kn,k。
接下来 k(n−1)k(n−1) 行，每 n−1n−1 行都表示一棵树，每行有一条边。
输出格式
输出到文件 seert.out 中。
nn 行，每行 nn 个数，表示点对 (i,j)(i,j) 的答案。
样例
Input 1
5 3 1 2 2 4 2 3 2 5 1 5 1 4 4 3 4 2 5 2 2 3 3 1 1 4
Output 1
1 4 4 3 4 4 1 3 4 4 4 3 1 4 5 3 4 4 1 5 4 4 5 5 1
样例解释
样例 1 解释
以 (1,2)(1,2) 为例，第一棵树中在路径上的点为 {1,2}{1,2}，第二棵树中在路径上的点为{1,2,4}{1,2,4}，第三棵树中在路径上的点为 {1,2,3}{1,2,3}，取并集得到 {1,2,3,4}{1,2,3,4}，大小为 44。
对于所有路径 (x,x)(x,x)，由于其会且只会经过 xx 一个点，所以并集大小是 11。
样例 2 输入 / 输出
见下发文件 ex_seert2.in/ans，该样例满足测试点 3∼63∼6 的限制。
样例 3 输入 / 输出
见下发文件 ex_seert3.in/ans，该样例满足测试点 1313 的限制。
数据范围
| 测试点编号 | n=n= | k≤k≤ | 特殊性质 |
|---|---|---|---|
| 1∼21∼2 | 5050 | 5050 | 无 |
| 3∼63∼6 | 399399 | 300300 | AA |
| 7∼117∼11 | 799799 | 300300 | AA |
| 1212 | 100100 | 300300 | 无 |
| 1313 | 400400 | 300300 | 无 |
| 14∼2014∼20 | 800800 | 300300 | 无 |
特殊性质 AA：满足这 kk 棵树均为链。注意 1 不一定是链的端点。
对于全部的测试点，保证：
- 1≤n≤800,1≤k≤3001≤n≤800,1≤k≤300。
- 1≤u,v≤n1≤u,v≤n。
提示：nn 的末尾数字可以帮助你快速判断特殊性质。
额外提示：请注意常数因子对程序运行效率的影响。
附件
有能力的大佬可以救助蒟蒻吗§(*￣▽￣*)§
`红温`代码
#include <bits/stdc++.h>
using namespace std;
int n, k;
vector<int> tags;
vector<bool> vis;
vector<vector<int>> cnt;
vector<vector<vector<int>>> edgs;
int randint(int _a, int _b)
{
static unsigned long long seed = random_device()();
static auto rng = mt19937_64(seed);
static auto res = uniform_int_distribution<int>(_a, _b);
return res(rng);
}
void bfs(int tree, int x)
{
int tag = randint(1, 32767);
queue<int> q;
vis[x] = 1;
tags[x] += tag;
q.push(x);
while (!q.empty())
{
int hd = q.front();
q.pop();
for (int targ : edgs[tree][hd])
{
if (vis[targ])
continue;
vis[targ] = 1;
tags[targ] += tag;
q.push(targ);
}
}
}
int main()
{
#ifdef ONLINE_JUDGE
freopen("seert.in", "r", stdin);
freopen("seert.out", "w", stdout);
#endif
cin.tie(&cout)->sync_with_stdio(0);
cin >> n >> k;
tags.resize(n + 1, 0);
vis.resize(n + 1, 0);
cnt.resize(n + 1, vector<int>(n + 1, n));
edgs.resize(k + 1, vector<vector<int>>(n + 1));
for (int i = 1; i <= k; i++)
{
for (int j = 1; j <= n - 1; j++)
{
int u, v;
cin >> u >> v;
edgs[i][u].push_back(v);
edgs[i][v].push_back(u);
}
}
for (int fr = 1; fr <= n; fr++)
{
fill(tags.begin(), tags.end(), 0);
for (int i = 1; i <= k; i++)
{
fill(vis.begin(), vis.end(), 0);
for (auto targ : edgs[i][fr])
{
vis[fr] = 1;
bfs(i, targ);
}
}
}
for (int fr = 1; fr <= n; fr++)
{
for (int to = 1; to <= n; to++)
{
if (tags[fr] == tags[to])
cnt[fr][to]--;
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
cout << (i == j ?: cnt[i][j]) << ' ';
cout << endl;
}
return 0;
}
较矢见谅