QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#408448#4814. Exciting Travelchenxinyang2006WA 2ms18252kbC++203.2kb2024-05-10 12:26:082024-05-10 12:26:09

Judging History

你现在查看的是最新测评结果

  • [2024-05-10 12:26:09]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:18252kb
  • [2024-05-10 12:26:08]
  • 提交

answer

#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
	if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
	if(x > y) x = y;
}

inline int popcnt(int x){
	return __builtin_popcount(x);
}

inline int ctz(int x){
	return __builtin_ctz(x);
}


/*ll power(ll p,int k = mod - 2){
	ll ans = 1;
	while(k){
		if(k % 2 == 1) ans = ans * p % mod;
		p = p * p % mod;
		k /= 2;	
	}
	return ans;
}*/
int n,m;

int cnt;
int head[200005];
struct eg{
	int to,nxt;
}edge[400005];

void make(int u,int v){
	edge[++cnt].to = v;
	edge[cnt].nxt = head[u];
	head[u] = cnt;
}

int N,fa[200005],siz[200005],dfn[200005],dep[200005],ST[20][200005];
inline int cmp(int x,int y){
	if(dep[x] < dep[y]) return x;
	return y;
}
inline int qry(int l,int r){
	int x = __lg(r - l + 1);
	return cmp(ST[x][l],ST[x][r - (1 << x) + 1]);
}
inline int LCA(int u,int v){
	if(u == v) return u;
	u = dfn[u];v = dfn[v];
	if(u > v) swap(u,v);
	return fa[qry(u + 1,v)];
}
void dfs(int u,int f){
	siz[u] = 1;
	dfn[u] = ++N;
	dep[u] = dep[f] + 1;
	fa[u] = f;
	ST[0][N] = u;
	for(int i = head[u];i;i = edge[i].nxt){
		int v = edge[i].to;
		if(v == f) continue;
		dfs(v,u);
		siz[u] += siz[v];
	}
}
int tree[200005];
#define lowbit(x) (x & (-x))
void upd(int pos,int C){
	while(pos <= n){
		tree[pos] += C;
		pos += lowbit(pos);
	}
}

int qry(int pos){
	int res = 0;
	while(pos){
		res += tree[pos];
		pos -= lowbit(pos);
	}
	return res;
}

int cov[200005];
void mdf(int u,int C){
	upd(dfn[u],C);
	if(dfn[u] + siz[u] <= n) upd(dfn[u] + siz[u],-C);
}

int chainsum(int u,int v,int d){
	return qry(dfn[u]) + qry(dfn[v]) - 2 * qry(dfn[d]) + cov[d];
}

void cover(int u){
	if(cov[u]) return;
	cov[u] = 1;
	mdf(u,1);
}

void dcover(int u){
	if(!cov[u]) return;
	cov[u] = 0;
	mdf(u,-1);
}

int idx[200005];
struct path{
	int u,v,d;
}S[200005];
bool cmp2(path p,path q){
	return dep[p.d] > dep[q.d];
}

int solve(int k){
	rep(i,1,k) cover(idx[i]);
	rep(i,1,k - 1){
		S[i].u = idx[i];S[i].v = idx[i + 1];S[i].d = LCA(idx[i],idx[i + 1]);
//		printf("%d ",S[i].d);
	}
//	printf("\n");
	sort(S + 1,S + k,cmp2);
	int ans = 0;
	rep(i,1,k - 1){
		if(chainsum(S[i].u,S[i].v,S[i].d) == 2){
			cover(S[i].d);
		}else{
			ans++;
		}
	}
	rep(i,1,k) dcover(idx[i]);
	rep(i,1,k - 1) dcover(S[i].d);
	return ans;
}

int main(){
//	freopen("test.in","r",stdin);
	scanf("%d%d",&n,&m);
	rep(i,1,n - 1){
		int u,v;
		scanf("%d%d",&u,&v);
		make(u,v);make(v,u);
	}
	dfs(1,0);
	rep(i,1,17){
		rep(j,1,n){
			if(j + (1 << i) - 1 > n) break;
			ST[i][j] = cmp(ST[i - 1][j],ST[i - 1][j + (1 << (i - 1))]);
		}
	}

	rep(i,1,m){
		int sz;
		scanf("%d",&sz);
		rep(j,1,sz) scanf("%d",&idx[j]);
		printf("%d\n",solve(sz));
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 13984kb

input:

5 3
1 2
1 3
2 4
2 5
3 1 4 5
4 1 2 4 3
4 2 4 5 1

output:

1
1
2

result:

ok 3 number(s): "1 1 2"

Test #2:

score: 0
Accepted
time: 2ms
memory: 18196kb

input:

8 7
1 2
1 3
1 4
2 5
2 6
5 7
3 8
1 4
2 1 7
3 5 2 4
4 3 6 1 4
6 5 3 7 1 2 4
6 4 8 3 5 6 1
7 2 8 5 4 6 1 3

output:

0
0
0
1
4
3
5

result:

ok 7 numbers

Test #3:

score: 0
Accepted
time: 0ms
memory: 14104kb

input:

10 10
8 3
10 4
1 2
10 9
9 1
4 8
1 5
6 3
2 7
1 10
1 3
5 4 6 8 3 10
5 1 6 3 8 7
1 5
4 3 8 1 4
1 10
3 4 6 9
1 6
3 7 5 3

output:

0
0
3
2
0
1
0
1
0
1

result:

ok 10 numbers

Test #4:

score: 0
Accepted
time: 0ms
memory: 9952kb

input:

1 1
1 1

output:

0

result:

ok 1 number(s): "0"

Test #5:

score: 0
Accepted
time: 1ms
memory: 7888kb

input:

1 0

output:


result:

ok 0 number(s): ""

Test #6:

score: 0
Accepted
time: 0ms
memory: 14120kb

input:

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

output:

1
0
4
0
0
0
2
0
0
4
0
0
0
4
4

result:

ok 15 numbers

Test #7:

score: 0
Accepted
time: 2ms
memory: 14080kb

input:

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

output:

0
3
1
3
0
0
0
0
0
0
0
5
6
1
6

result:

ok 15 numbers

Test #8:

score: 0
Accepted
time: 2ms
memory: 14068kb

input:

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

output:

1
1
0
2
6
3
0
0
0
0
7
0
0
5
0

result:

ok 15 numbers

Test #9:

score: -100
Wrong Answer
time: 2ms
memory: 18252kb

input:

1000 500
685 415
28 527
771 396
201 538
604 162
631 66
144 596
788 378
919 59
737 550
471 413
3 590
891 52
886 705
350 238
164 224
554 358
909 150
354 441
310 756
380 661
380 867
601 318
197 204
993 673
118 624
249 539
841 737
742 853
250 566
543 663
981 243
60 120
976 801
750 2
694 8
935 831
381 48...

output:

0
3
0
3
4
2
2
0
2
0
4
0
1
4
5
2
0
12
0
14
3
3
5
3
0
0
2
0
4
9
5
5
1
0
40
12
0
18
4
1
1
6
0
7
3
0
0
14
5
1
3
8
5
0
4
0
5
7
2
5
6
0
5
0
1
2
7
3
0
0
6
0
1
8
4
1
11
0
1
0
8
3
2
0
1
2
0
3
9
5
13
2
0
4
2
0
4
1
14
1
4
4
4
0
1
1
10
2
2
0
0
4
10
2
3
10
4
0
13
6
0
19
3
4
9
2
10
6
1
0
0
3
0
0
5
12
5
2
2
1
9
15...

result:

wrong answer 135th numbers differ - expected: '6', found: '5'