#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define inf 1e18
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define pi 3.14159265359
#define TASKNAME "railway"
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
const int MAXN = 3e5 + 9;
vector<int> g[MAXN];
struct Query{
int num;
vector<int> QueryVert;
} Q[MAXN];
int n, m, k, S;
ii edge[MAXN], par[MAXN];
int QueryVert[MAXN], depth[MAXN], pre[MAXN], FreqCount[MAXN];
int tmpPar[MAXN];
namespace subtask1{
bool checkSubtask1(){
int S = 0;
for(int i = 1; i <= m; i++){
S += Q[i].num;
}
return S <= 2000 and n <= 10000;
}
void dfs(int u, int p){
for(auto id: g[u]){
int v = edge[id].se + edge[id].fi - u;
if (v == p) continue;
par[v] = {u, id};
depth[v] = depth[u] + 1;
dfs(v, u);
}
}
void CountAnswer(int u, int p){
for(auto id: g[u]){
int v = edge[id].se + edge[id].fi - u;
if (v == p) continue;
CountAnswer(v, u);
FreqCount[id] += pre[v];
pre[u] += pre[v];
}
}
int root(int u){
if (u == tmpPar[u]) return u;
else return tmpPar[u] = root(tmpPar[u]);
}
void go(int u, int v){
while(u != v){
u = root(u);
v = root(v);
if (u == v) break;
if (depth[u] < depth[v]) swap(u, v);
FreqCount[par[u].se]++;
tmpPar[u] = par[u].fi;
}
}
void solveSubtask1(){
dfs(1, -1);
for(int i = 1; i <= m; i++){
int num = Q[i].num;
iota(tmpPar + 1, tmpPar + 1 + n, 1);
for(int j = 0; j < num; j++){
for(int k = j + 1; k < num; k++){
go(Q[i].QueryVert[j], Q[i].QueryVert[k]);
}
}
}
CountAnswer(1, -1);
vector<int> ans;
for(int i = 1; i < n; i++){
if (FreqCount[i] >= k) ans.pb(i);
}
cout << ans.size() << endl;
for(auto x: ans){
cout << x << ' ';
}
cout << endl;
}
}
namespace subtask2{
bool checkSubtask2(){
return true;
}
vector<int> etour = {0};
vector<int> virtualTree[MAXN];
int in[MAXN], out[MAXN], FreqCount[MAXN], dfsTime = 0;
ii P[MAXN * 2][21];
void dfs(int u, int p){
etour.pb(u);
in[u] = ++dfsTime;
for(auto id: g[u]){
int v = edge[id].se + edge[id].fi - u;
if (v == p) continue;
depth[v] = depth[u] + 1;
par[v] = {u, id};
dfs(v, u);
etour.pb(u);
dfsTime++;
}
out[u] = dfsTime;
}
ii getrange(int l, int r){
int x = log2(r - l + 1);
return min(P[l][x], P[r - (1 << x) + 1][x]);
}
ii lca(int u, int v){
return getrange(min(in[u], in[v]), max(in[u], in[v]));
}
bool inTree(int u, int v){ //Check if vertice v lie in the subtree of the vertice u
return in[v] >= in[u] and in[v] <= out[u];
}
void VirtualTree(int num, vector<int> &Vertice){
sort(Vertice.begin(), Vertice.end(), [&](const int &u, const int &v){
return in[u] < in[v];
});
for(int i = 0; i < num - 1; i++){
int u = Vertice[i];
int v = Vertice[i + 1];
ii acs = lca(u, v);
Vertice.pb(acs.se);
}
sort(Vertice.begin(), Vertice.end(), [&](const int &u, const int &v){
return in[u] < in[v];
});
Vertice.erase(unique(Vertice.begin(), Vertice.end()), Vertice.end());
//
// for(int i = 0; i < Vertice.size(); i++){
// cout << Vertice[i] << ' ';
// }
// cout << endl;
vector<int> curStack;
for(int i = 0; i < Vertice.size(); i++){
if (curStack.size() == 0) curStack.pb(Vertice[i]);
else{
int x = curStack.back();
while(curStack.size() > 0 and !inTree(curStack.back(), Vertice[i])) {
curStack.pop_back();
}
// cout << curStack.back() << ' ' << Vertice[i] << endl;
pre[curStack.back()]--;
pre[Vertice[i]]++;
curStack.pb(Vertice[i]);
}
}
}
void CountAnswer(int u, int p){
for(auto id: g[u]){
int v = edge[id].se + edge[id].fi - u;
if (v == p) continue;
CountAnswer(v, u);
FreqCount[id] += pre[v];
pre[u] += pre[v];
}
}
void solveSubtask2(){
dfs(1, -1);
// for(int i = 0; i < etour.size(); i++){
// cout << etour[i] << ' ';
// }
// cout << endl;
//
// for(int i = 1; i <= n; i++){
// cout << in[i] << ' ' << out[i] << endl;
// }
//Sparse Table For LCA
for(int i = 1; i < etour.size(); i++){
P[i][0] = ii(depth[etour[i]], etour[i]);
}
for(int i = 1; i <= 18; i++){
for(int j = 1; j + (1 << i) - 1 < etour.size(); j++){
P[j][i] = min(P[j][i - 1], P[j + (1 << (i - 1))][i - 1]);
}
}
//Handle Queries
for(int i = 1; i <= m; i++){
int num = Q[i].num;
VirtualTree(num, Q[i].QueryVert); //Using Virtual Tree to handle Queries.
}
CountAnswer(1, -1);
vector<int> ans;
for(int i = 1; i < n; i++){
// cout << FreqCount[i] << ' ';
if (FreqCount[i] >= k) ans.pb(i);
}
// cout << endl;
cout << ans.size() << endl;
for(auto x: ans){
cout << x << ' ';
}
cout << endl;
}
}
main()
{
fast;
if (fopen(TASKNAME".inp","r")){
freopen(TASKNAME".inp","r",stdin);
freopen(TASKNAME".out","w",stdout);
}
cin >> n >> m >> k;
for(int i = 1; i < n; i++){
int u, v;
cin >> u >> v;
g[u].pb(i);
g[v].pb(i);
edge[i] = {u, v};
}
for(int i = 1; i <= m; i++){
cin >> Q[i].num;
for(int j = 0; j < Q[i].num; j++){
int x;
cin >> x;
Q[i].QueryVert.pb(x);
}
}
if (subtask1::checkSubtask1()) return subtask1::solveSubtask1(), 0;
if (subtask2::checkSubtask2()) return subtask2::solveSubtask2(), 0;
}
/**
Warning:
- MLE / TLE?
- Gioi han mang?
- Gia tri max phai luon gan cho -INF
- long long co can thiet khong?
- tran mang.
- code can than hon
- Nho sinh test de tranh RTE / TLE
--> Coi lai truoc khi nop
**/
Compilation message
railway.cpp: In function 'void subtask2::VirtualTree(long long int, std::vector<long long int>&)':
railway.cpp:175:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
175 | for(int i = 0; i < Vertice.size(); i++){
| ~~^~~~~~~~~~~~~~~~
railway.cpp:178:22: warning: unused variable 'x' [-Wunused-variable]
178 | int x = curStack.back();
| ^
railway.cpp: In function 'void subtask2::solveSubtask2()':
railway.cpp:214:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
214 | for(int i = 1; i < etour.size(); i++){
| ~~^~~~~~~~~~~~~~
railway.cpp:219:45: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
219 | for(int j = 1; j + (1 << i) - 1 < etour.size(); j++){
| ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
railway.cpp: At global scope:
railway.cpp:247:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
247 | main()
| ^~~~
railway.cpp: In function 'int main()':
railway.cpp:251:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
251 | freopen(TASKNAME".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:252:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
252 | freopen(TASKNAME".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
31580 KB |
Output is correct |
2 |
Correct |
10 ms |
34396 KB |
Output is correct |
3 |
Correct |
10 ms |
34356 KB |
Output is correct |
4 |
Correct |
7 ms |
31580 KB |
Output is correct |
5 |
Correct |
9 ms |
31580 KB |
Output is correct |
6 |
Correct |
18 ms |
34740 KB |
Output is correct |
7 |
Correct |
12 ms |
34392 KB |
Output is correct |
8 |
Correct |
12 ms |
34140 KB |
Output is correct |
9 |
Correct |
13 ms |
34344 KB |
Output is correct |
10 |
Correct |
7 ms |
31652 KB |
Output is correct |
11 |
Correct |
6 ms |
31580 KB |
Output is correct |
12 |
Correct |
8 ms |
31580 KB |
Output is correct |
13 |
Correct |
6 ms |
31580 KB |
Output is correct |
14 |
Correct |
6 ms |
31580 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
31580 KB |
Output is correct |
2 |
Correct |
10 ms |
34396 KB |
Output is correct |
3 |
Correct |
10 ms |
34356 KB |
Output is correct |
4 |
Correct |
7 ms |
31580 KB |
Output is correct |
5 |
Correct |
9 ms |
31580 KB |
Output is correct |
6 |
Correct |
18 ms |
34740 KB |
Output is correct |
7 |
Correct |
12 ms |
34392 KB |
Output is correct |
8 |
Correct |
12 ms |
34140 KB |
Output is correct |
9 |
Correct |
13 ms |
34344 KB |
Output is correct |
10 |
Correct |
7 ms |
31652 KB |
Output is correct |
11 |
Correct |
6 ms |
31580 KB |
Output is correct |
12 |
Correct |
8 ms |
31580 KB |
Output is correct |
13 |
Correct |
6 ms |
31580 KB |
Output is correct |
14 |
Correct |
6 ms |
31580 KB |
Output is correct |
15 |
Correct |
30 ms |
49368 KB |
Output is correct |
16 |
Correct |
29 ms |
49368 KB |
Output is correct |
17 |
Correct |
29 ms |
49488 KB |
Output is correct |
18 |
Correct |
12 ms |
47576 KB |
Output is correct |
19 |
Correct |
14 ms |
34396 KB |
Output is correct |
20 |
Correct |
22 ms |
49624 KB |
Output is correct |
21 |
Correct |
25 ms |
49364 KB |
Output is correct |
22 |
Correct |
7 ms |
31576 KB |
Output is correct |
23 |
Correct |
11 ms |
34348 KB |
Output is correct |
24 |
Correct |
10 ms |
34392 KB |
Output is correct |
25 |
Correct |
6 ms |
31580 KB |
Output is correct |
26 |
Correct |
7 ms |
31580 KB |
Output is correct |
27 |
Correct |
18 ms |
34908 KB |
Output is correct |
28 |
Correct |
12 ms |
34392 KB |
Output is correct |
29 |
Correct |
12 ms |
34136 KB |
Output is correct |
30 |
Correct |
13 ms |
34140 KB |
Output is correct |
31 |
Correct |
6 ms |
31580 KB |
Output is correct |
32 |
Correct |
7 ms |
31580 KB |
Output is correct |
33 |
Correct |
7 ms |
31576 KB |
Output is correct |
34 |
Correct |
6 ms |
31580 KB |
Output is correct |
35 |
Correct |
6 ms |
31580 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
125 ms |
125868 KB |
Output is correct |
2 |
Correct |
8 ms |
31580 KB |
Output is correct |
3 |
Correct |
102 ms |
125124 KB |
Output is correct |
4 |
Correct |
98 ms |
123852 KB |
Output is correct |
5 |
Correct |
94 ms |
126396 KB |
Output is correct |
6 |
Correct |
98 ms |
127176 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
95 ms |
120516 KB |
Output is correct |
2 |
Correct |
105 ms |
116936 KB |
Output is correct |
3 |
Correct |
112 ms |
116624 KB |
Output is correct |
4 |
Correct |
110 ms |
116676 KB |
Output is correct |
5 |
Correct |
111 ms |
116556 KB |
Output is correct |
6 |
Correct |
95 ms |
120664 KB |
Output is correct |
7 |
Correct |
97 ms |
120644 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
95 ms |
120516 KB |
Output is correct |
2 |
Correct |
105 ms |
116936 KB |
Output is correct |
3 |
Correct |
112 ms |
116624 KB |
Output is correct |
4 |
Correct |
110 ms |
116676 KB |
Output is correct |
5 |
Correct |
111 ms |
116556 KB |
Output is correct |
6 |
Correct |
95 ms |
120664 KB |
Output is correct |
7 |
Correct |
97 ms |
120644 KB |
Output is correct |
8 |
Correct |
105 ms |
120272 KB |
Output is correct |
9 |
Correct |
109 ms |
120320 KB |
Output is correct |
10 |
Correct |
95 ms |
125604 KB |
Output is correct |
11 |
Correct |
100 ms |
125672 KB |
Output is correct |
12 |
Correct |
90 ms |
115612 KB |
Output is correct |
13 |
Correct |
87 ms |
115652 KB |
Output is correct |
14 |
Correct |
108 ms |
117440 KB |
Output is correct |
15 |
Correct |
107 ms |
116924 KB |
Output is correct |
16 |
Correct |
107 ms |
116676 KB |
Output is correct |
17 |
Correct |
118 ms |
116672 KB |
Output is correct |
18 |
Correct |
128 ms |
116760 KB |
Output is correct |
19 |
Correct |
102 ms |
116932 KB |
Output is correct |
20 |
Correct |
102 ms |
121180 KB |
Output is correct |
21 |
Correct |
101 ms |
121540 KB |
Output is correct |
22 |
Correct |
110 ms |
121028 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
31580 KB |
Output is correct |
2 |
Correct |
10 ms |
34396 KB |
Output is correct |
3 |
Correct |
10 ms |
34356 KB |
Output is correct |
4 |
Correct |
7 ms |
31580 KB |
Output is correct |
5 |
Correct |
9 ms |
31580 KB |
Output is correct |
6 |
Correct |
18 ms |
34740 KB |
Output is correct |
7 |
Correct |
12 ms |
34392 KB |
Output is correct |
8 |
Correct |
12 ms |
34140 KB |
Output is correct |
9 |
Correct |
13 ms |
34344 KB |
Output is correct |
10 |
Correct |
7 ms |
31652 KB |
Output is correct |
11 |
Correct |
6 ms |
31580 KB |
Output is correct |
12 |
Correct |
8 ms |
31580 KB |
Output is correct |
13 |
Correct |
6 ms |
31580 KB |
Output is correct |
14 |
Correct |
6 ms |
31580 KB |
Output is correct |
15 |
Correct |
30 ms |
49368 KB |
Output is correct |
16 |
Correct |
29 ms |
49368 KB |
Output is correct |
17 |
Correct |
29 ms |
49488 KB |
Output is correct |
18 |
Correct |
12 ms |
47576 KB |
Output is correct |
19 |
Correct |
14 ms |
34396 KB |
Output is correct |
20 |
Correct |
22 ms |
49624 KB |
Output is correct |
21 |
Correct |
25 ms |
49364 KB |
Output is correct |
22 |
Correct |
7 ms |
31576 KB |
Output is correct |
23 |
Correct |
11 ms |
34348 KB |
Output is correct |
24 |
Correct |
10 ms |
34392 KB |
Output is correct |
25 |
Correct |
6 ms |
31580 KB |
Output is correct |
26 |
Correct |
7 ms |
31580 KB |
Output is correct |
27 |
Correct |
18 ms |
34908 KB |
Output is correct |
28 |
Correct |
12 ms |
34392 KB |
Output is correct |
29 |
Correct |
12 ms |
34136 KB |
Output is correct |
30 |
Correct |
13 ms |
34140 KB |
Output is correct |
31 |
Correct |
6 ms |
31580 KB |
Output is correct |
32 |
Correct |
7 ms |
31580 KB |
Output is correct |
33 |
Correct |
7 ms |
31576 KB |
Output is correct |
34 |
Correct |
6 ms |
31580 KB |
Output is correct |
35 |
Correct |
6 ms |
31580 KB |
Output is correct |
36 |
Correct |
125 ms |
125868 KB |
Output is correct |
37 |
Correct |
8 ms |
31580 KB |
Output is correct |
38 |
Correct |
102 ms |
125124 KB |
Output is correct |
39 |
Correct |
98 ms |
123852 KB |
Output is correct |
40 |
Correct |
94 ms |
126396 KB |
Output is correct |
41 |
Correct |
98 ms |
127176 KB |
Output is correct |
42 |
Correct |
95 ms |
120516 KB |
Output is correct |
43 |
Correct |
105 ms |
116936 KB |
Output is correct |
44 |
Correct |
112 ms |
116624 KB |
Output is correct |
45 |
Correct |
110 ms |
116676 KB |
Output is correct |
46 |
Correct |
111 ms |
116556 KB |
Output is correct |
47 |
Correct |
95 ms |
120664 KB |
Output is correct |
48 |
Correct |
97 ms |
120644 KB |
Output is correct |
49 |
Correct |
105 ms |
120272 KB |
Output is correct |
50 |
Correct |
109 ms |
120320 KB |
Output is correct |
51 |
Correct |
95 ms |
125604 KB |
Output is correct |
52 |
Correct |
100 ms |
125672 KB |
Output is correct |
53 |
Correct |
90 ms |
115612 KB |
Output is correct |
54 |
Correct |
87 ms |
115652 KB |
Output is correct |
55 |
Correct |
108 ms |
117440 KB |
Output is correct |
56 |
Correct |
107 ms |
116924 KB |
Output is correct |
57 |
Correct |
107 ms |
116676 KB |
Output is correct |
58 |
Correct |
118 ms |
116672 KB |
Output is correct |
59 |
Correct |
128 ms |
116760 KB |
Output is correct |
60 |
Correct |
102 ms |
116932 KB |
Output is correct |
61 |
Correct |
102 ms |
121180 KB |
Output is correct |
62 |
Correct |
101 ms |
121540 KB |
Output is correct |
63 |
Correct |
110 ms |
121028 KB |
Output is correct |
64 |
Correct |
112 ms |
121032 KB |
Output is correct |
65 |
Correct |
113 ms |
116616 KB |
Output is correct |
66 |
Correct |
109 ms |
116732 KB |
Output is correct |
67 |
Correct |
110 ms |
116932 KB |
Output is correct |
68 |
Correct |
98 ms |
114964 KB |
Output is correct |
69 |
Correct |
84 ms |
115004 KB |
Output is correct |
70 |
Correct |
118 ms |
121688 KB |
Output is correct |
71 |
Correct |
99 ms |
120260 KB |
Output is correct |
72 |
Correct |
6 ms |
31832 KB |
Output is correct |
73 |
Correct |
10 ms |
34444 KB |
Output is correct |
74 |
Correct |
11 ms |
34344 KB |
Output is correct |
75 |
Correct |
7 ms |
31580 KB |
Output is correct |
76 |
Correct |
7 ms |
31580 KB |
Output is correct |
77 |
Correct |
20 ms |
34908 KB |
Output is correct |
78 |
Correct |
12 ms |
34396 KB |
Output is correct |
79 |
Correct |
12 ms |
34140 KB |
Output is correct |
80 |
Correct |
12 ms |
34392 KB |
Output is correct |
81 |
Correct |
6 ms |
31656 KB |
Output is correct |
82 |
Correct |
6 ms |
31580 KB |
Output is correct |
83 |
Correct |
7 ms |
31580 KB |
Output is correct |
84 |
Correct |
7 ms |
31580 KB |
Output is correct |
85 |
Correct |
7 ms |
31576 KB |
Output is correct |
86 |
Correct |
32 ms |
49360 KB |
Output is correct |
87 |
Correct |
32 ms |
49356 KB |
Output is correct |
88 |
Correct |
28 ms |
49624 KB |
Output is correct |
89 |
Correct |
13 ms |
47580 KB |
Output is correct |
90 |
Correct |
14 ms |
34396 KB |
Output is correct |
91 |
Correct |
23 ms |
49632 KB |
Output is correct |
92 |
Correct |
25 ms |
49368 KB |
Output is correct |
93 |
Correct |
6 ms |
31580 KB |
Output is correct |
94 |
Correct |
99 ms |
126036 KB |
Output is correct |
95 |
Correct |
99 ms |
125120 KB |
Output is correct |
96 |
Correct |
97 ms |
123896 KB |
Output is correct |
97 |
Correct |
96 ms |
126328 KB |
Output is correct |
98 |
Correct |
129 ms |
127176 KB |
Output is correct |
99 |
Correct |
106 ms |
116676 KB |
Output is correct |
100 |
Correct |
107 ms |
116672 KB |
Output is correct |
101 |
Correct |
106 ms |
116676 KB |
Output is correct |
102 |
Correct |
108 ms |
117608 KB |
Output is correct |
103 |
Correct |
95 ms |
120516 KB |
Output is correct |
104 |
Correct |
99 ms |
121284 KB |
Output is correct |
105 |
Correct |
94 ms |
120576 KB |
Output is correct |
106 |
Correct |
105 ms |
120488 KB |
Output is correct |
107 |
Correct |
99 ms |
120256 KB |
Output is correct |
108 |
Correct |
97 ms |
125716 KB |
Output is correct |
109 |
Correct |
96 ms |
125660 KB |
Output is correct |
110 |
Correct |
96 ms |
115904 KB |
Output is correct |
111 |
Correct |
85 ms |
115652 KB |
Output is correct |
112 |
Correct |
108 ms |
116924 KB |
Output is correct |
113 |
Correct |
134 ms |
116744 KB |
Output is correct |