UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#213522#2769. 覆盖nodgd00ms1324kbC++112.2kb2024-11-12 19:45:372024-11-12 23:19:43

answer

#include <bits/stdc++.h>

using namespace std;

namespace FastRead{
	char buf[1000005], *s = buf, *t = buf, ch, f;
	#define gc() s == t && (t = (s = buf) + fread(buf, 1, 1000000, stdin), s == t) ? EOF : *s ++ 
	template <typename T>
	inline void Read(T &x)
	{
		x = f = 0, ch = gc();
		while(ch < '0' || ch > '9')
		{
			if(ch == '-') f = 1;
			ch = gc();
		}
		while('0' <= ch && ch <= '9') x = x * 10 + ch - 48, ch = gc();
		f && (x = -x);
	}
};
using FastRead::Read;

const int N = 2e6 + 5, K = 22;

int n, m;
int la[N], ne[N * 2], en[N * 2], idx;
int fa[N][K], dep[N], in[N], out[N], dfst;
struct Node{
	int u, v, w, d;
	bool operator <(const Node &w) const
	{
		return d > w.d;
	}
}x[N];
int cnt, vis[N], c[N];

inline void Add(int a, int b)
{
	ne[ ++ idx] = la[a];
	la[a] = idx;
	en[idx] = b;
}
inline void DFS(int u, int f)
{
	fa[u][0] = f, dep[u] = dep[f] + 1;
	for(int i = 1; i < K; i ++ ) fa[u][i] = fa[fa[u][i - 1]][i - 1];
	in[u] = ++ dfst;
	for(int i = la[u]; i; i = ne[i])
	{
		int v = en[i];
		if(v != f) DFS(v, u);
	}
	out[u] = dfst;
}
inline int LCA(int u, int v)
{
	if(dep[u] < dep[v]) swap(u, v);
	for(int i = K - 1; i >= 0; i -- )
		if(dep[fa[u][i]] >= dep[v])
			u = fa[u][i];
	if(u == v) return u;
	for(int i = K - 1; i >= 0; i -- )
		if(fa[u][i] != fa[v][i])
			u = fa[u][i], v = fa[v][i];
	return fa[u][0];
}

inline void Modify(int i, int d)
{
	for(; i <= n; i += i & -i) c[i] += d;
}
inline int Sum(int i)
{
	int s = 0;
	for(; i; i &= i - 1) s += c[i];
	return s;
}

int main()
{
	Read(n), Read(m);
	for(int i = 1; i < n; i ++ )
	{
		int a, b;
		Read(a), Read(b);
		Add(a, b), Add(b, a);
	}
	DFS(1, 0);
	for(int i = 1; i <= m; i ++ )
	{
		Read(x[i].u), Read(x[i].v);
		x[i].w = LCA(x[i].u, x[i].v);
		x[i].d = dep[x[i].w];
	}
	sort(x + 1, x + m + 1);
	for(int i = 1; i <= m; i ++ )
	{
//		printf("*%d %d %d\n", x[i].u, x[i].v, x[i].w);
		if(Sum(in[x[i].u]) + Sum(in[x[i].v]) - Sum(in[x[i].w]) - Sum(in[fa[x[i].w][0]]) == 0)
		{
			vis[x[i].w] = 1;
			cnt ++ ;
			Modify(in[x[i].w], 1);
			Modify(out[x[i].w] + 1, -1);
		}
	}
	printf("%d\n", cnt);
	for(int i = 1; i <= n; i ++ ) if(vis[i]) printf("%d ", i);
	puts("");
	return 0;
}

Details

小提示:点击横条可展开更详细的信息

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

score: 0
Time Limit Exceeded

input:

20
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 13
17 15
18 16
19 17
20 18
...

output:


result:


Subtask #2:

score: 0
Wrong Answer

Test #11:

score: 0
Wrong Answer
time: 0ms
memory: 1324kb

input:

1000
2 1
3 2
4 3
5 4
6 3
7 6
8 7
9 8
10 9
11 10
12 5
13 11
14 13
15 14
16 15
17 12
18 16
19 18
20 19...

output:

1
80 

result:

wrong answer Arrangement not valid

Subtask #3:

score: 0
Time Limit Exceeded

Test #21:

score: 0
Time Limit Exceeded

input:

2000000
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 11
15 14
16 13
17 15
18 16
19 17
2...

output:


result: