QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#56906#4814. Exciting TravelKING_UT#WA 8ms4324kbC++205.9kb2022-10-21 20:40:492022-10-21 20:40:50

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-21 20:40:50]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:4324kb
  • [2022-10-21 20:40:49]
  • 提交

answer

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

using ll=long long;
#define int ll

#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)

#define bg begin()
#define ed end()
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) x.bg,x.ed
#define si(x) (int)x.size()

template<class t>using vc=vector<t>;
template<class t>using vvc=vc<vc<t>>;

template<class t,class u>bool chmin(t&a,u b){
	if(a>b){a=b;return true;}
	else return false;
}
template<class t,class u>bool chmax(t&a,u b){
	if(a<b){a=b;return true;}
	else return false;
}
template<class t>using vc=vector<t>;
template<class t>using vvc=vector<vector<t>>;
using vi=vc<int>;
using pi=pair<int,int>;
#define a first
#define b second

template<class E>
struct HLD{
	vvc<E>g;
	int n,rt,cnt;
	vi sub,in,out,par,head,dep,hei,ni;
	vvc<E>bin;
	vc<E>pe;
	int dfs1(int v,int p,int d){
		par[v]=p;
		dep[v]=d;
		for(auto itr=g[v].begin();itr!=g[v].end();itr++)
			if(*itr==p){
				pe[v]=*itr;
				g[v].erase(itr);
				break;
			}
		for(auto &e:g[v]){
			pe[e]=e;
			sub[v]+=dfs1(e,v,d+1);
			if(sub[g[v][0]]<sub[e]) swap(g[v][0],e);
		}
		return sub[v];
	}
	void dfs2(int v,int h){
		in[v]=cnt++;
		head[v]=h;
		for(auto to:g[v])
			dfs2(to,to==g[v][0]?h:to);
		out[v]=cnt;
		if(si(g[v])) hei[v]=hei[g[v][0]]+1;
	}
	HLD(){}
	HLD(const vvc<E>&gg,int rr):g(gg),n(g.size()),rt(rr),cnt(0),
		sub(n,1),in(n),out(n),par(n,-1),head(n),dep(n),hei(n,1),ni(n),
		pe(n){
			dfs1(rt,-1,0);
			dfs2(rt,rt);
			rep(i,n)ni[in[i]]=i;
			bin.resize(20);
			bin[0] = par;
			rep(j, 19){
				bin[j+1].resize(n);
				rep(i, n){
					if(bin[j][i]==-1) bin[j+1][i]=-1;
					else bin[j+1][i]=bin[j][bin[j][i]];
				}
			}
	}
	int up(int v,int a){
		rep(j, 20){
			if(((a>>j)&1)) v = bin[j][v];
		}
		return v;
	}
	int lca(int a,int b){
		while(head[a]!=head[b]){
			if(dep[head[a]]>dep[head[b]]){
				swap(a,b);
			}
			b=par[head[b]];
		}
		if(dep[a]>dep[b]) swap(a,b);
		return a;
	}
	int len(int a,int b){
		return dep[a]+dep[b]-dep[lca(a,b)]*2;
	}
	bool asde(int a,int b){
		return in[a]<=in[b] and out[b]<=out[a];
	}
	
	vi index;
	pair<vi,vc<pi>>tree_compress(vi vs){
		if(index.size()==0) index.resize(n);
		auto comp=[&](int x,int y){
			return in[x]<in[y];
		};
		sort(vs.begin(), vs.end(), comp);
		vs.erase(unique(vs.begin(), vs.end()),vs.end());
		int k=vs.size();
		rep(i,k-1){
			vs.pb(lca(vs[i],vs[i+1]));
		}
		sort(vs.begin(), vs.end(), comp);
		vs.erase(unique(vs.begin(), vs.end()),vs.end());
		k=vs.size();
		rep(i,k)index[vs[i]]=i;
		vc<pi>es;
		rng(i,1,k){
			int p=lca(vs[i-1],vs[i]);
			es.eb(i,index[p]);
		}
		return mp(vs, es);
	}
};
struct BIT{
	vc<int>b;
	int sz;
	void init(int a){
		sz = a+3;
		b.clear();
		b.assign(sz, 0);
	}
	void add(int i, int v){
		i ++;
		for(;i<sz;i+=i&-i) b[i] += v;
	}
	int sum(int i){
		i ++;
		int ret=0;
		for(;i;i-=i&-i) ret += b[i];
		return ret;
	}
}bit;
using P=pi;
int sol(vc<int>A, vc<int>info, vc<pi>edge){
	unordered_map<int,int>M;
	rep(i, A.size()){
		M[A[i]] = i;
	}
	int n = A.size();
	vc<int>imp(n);
	for(auto v:info) imp[M[v]] = 1;
	
	vvc<int>g; g.resize(n);
	for(auto uv:edge){
		g[uv.a].pb(uv.b);
		g[uv.b].pb(uv.a);
	}
	HLD<int>h2(g, 0);
	vc<int>sum2(n);
	auto dfs0=[&](int v,int u,auto dfs0)->void{
		sum2[v] += imp[v];
		for(auto to:g[v]){
			if(to==u)continue;
			sum2[to] = sum2[v];
			dfs0(to,v,dfs0);
		}
	};
	dfs0(0,-1,dfs0);
	//for(auto x:A) cout << x << " "; cout << endl;
	//for(auto x:info) cout << x << " "; cout << endl;
	//for(auto x:edge) cout << x.a << " " << x.b << endl;
	//rep(i, n) cout << sum2[i] << " "; cout << endl;
	vvc<P>q; q.resize(n);
	int pre=0;
	rng(i, 1, info.size()){
		int u = M[info[i-1]];
		int v = M[info[i]];
		int w = h2.lca(u, v);
		if(sum2[u]+sum2[v]-sum2[w]*2+imp[w] != 2) continue;
		//cerr<<info[i-1]<<" "<<info[i]<<endl;
		int L = h2.len(u, v);
			
			if(L == 1) pre++;
			else if(L == 2){
				int mid;
				if(u != w) mid=(h2.up(u, 1));
				else mid=(h2.up(v, 1));
				q[mid].eb(mid, mid);
			}
			else{
				int mid1, mid2;
				if(u != w) mid1=(h2.up(u, 1));
				else mid1=(h2.up(v, L-1));
				
				if(v != w) mid2=(h2.up(v, 1));
				else mid2=(h2.up(u, L-1));
				
				q[h2.lca(mid1, mid2)].eb(mid1, mid2);
			}
	}
	bit.init(n+1);
	vc<int>sum(n), dp(n);
	
	
	auto dfs=[&](int v, int u, auto dfs) -> void{
		for(auto to:g[v]){
			if(to == u) continue;
			dfs(to, v, dfs);
			sum[v] += dp[to];
		}
		dp[v] = sum[v];
		for(auto edd:q[v]){
			int tmp=1;
			int x[2]={edd.a, edd.b};
			rep(_, 2){
				int p = x[_];
				if(p == v) continue;
				int L = h2.len(p, v);
				int ch = h2.up(p, L-1);
				tmp += sum[ch]-dp[ch];
				if(L > 1){
					tmp += bit.sum(h2.in[p]);
					tmp -= bit.sum(h2.in[ch]);
				}
			}
			if(dp[v] < sum[v]+tmp) dp[v] = sum[v]+tmp;
		}
		bit.add(h2.in[v], sum[v]-dp[v]);
		bit.add(h2.out[v], sum[v]-dp[v]);
	};
	dfs(0, -1, dfs);
	return dp[0]+pre;
}
void slv(){
	int n,m;
	cin>>n>>m;
	vvc<int>g; g.resize(n);
	rep(i,n-1){
		int u,v;cin>>u>>v;
		u--; v--;
		g[u].pb(v);
		g[v].pb(u);
	}
	HLD<int>h1(g, 0);
	
	rep(_, m){
		int k; cin >> k;
		vc<int>vec(k);
		rep(i, k) cin >> vec[i];
		if(k <= 2){
			cout << 0 << '\n';
			continue;
		}
		rep(i, k) vec[i]--;
		vc<int>A = vec;
		rep(i, k-1){
			int u = vec[i];
			int v = vec[i+1];
			int L = h1.len(u, v);
			
			if(L == 1) continue;
			else if(L == 2){
				int w = h1.lca(u, v);
				if(u != w) A.pb(h1.up(u, 1));
				else A.pb(h1.up(v, 1));
			}
			else{
				int w = h1.lca(u, v);
				if(u != w) A.pb(h1.up(u, 1));
				else A.pb(h1.up(v, L-1));
				//cout<<u<<" "<<v<<endl;
				//cout<<A.back()<<" ";
				
				if(v != w) A.pb(h1.up(v, 1));
				else A.pb(h1.up(u, L-1));
				//cout<<A.back()<<endl;
				//cout<<"_____"<<endl;
			}
		}
		//for(auto a:A) cout<<a<<" ";cout<<endl;
		auto ret = h1.tree_compress(A);
		//for(auto a:ret.a) cout<<a<<" ";cout<<endl;
		//for(auto b:ret.b) cout<<b.a<<" "<<b.b<<endl;
		cout << k-1-sol(ret.a, vec, ret.b) << '\n';
	}
}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	
	int t;t=1;//cin>>t;
	while(t--) slv();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3672kb

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: 3564kb

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: 2ms
memory: 3712kb

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: 2ms
memory: 3552kb

input:

1 1
1 1

output:

0

result:

ok 1 number(s): "0"

Test #5:

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

input:

1 0

output:


result:

ok 0 number(s): ""

Test #6:

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

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: 1ms
memory: 3708kb

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: 3624kb

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: 8ms
memory: 4324kb

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
5
3
3
0
2
0
4
0
1
5
6
2
0
14
0
14
4
3
6
3
0
0
3
0
4
9
5
5
1
0
41
13
0
19
4
2
1
6
0
7
3
0
0
14
5
1
3
8
6
0
5
0
6
7
2
6
6
0
5
0
2
2
7
3
0
0
7
0
1
9
5
1
11
0
1
0
8
3
3
0
1
2
0
3
9
5
13
2
0
5
2
0
5
1
14
1
4
4
4
0
1
1
10
2
2
0
0
6
10
2
4
12
4
0
13
7
0
20
4
5
9
2
11
7
1
0
0
3
0
0
7
13
5
2
2
1
9
16...

result:

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