// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
/*
find my code templates at https://github.com/galencolin/cp-templates
also maybe subscribe please thanks
*/
#define send {ios_base::sync_with_stdio(false);}
#define help {cin.tie(NULL);}
#define f first
#define s second
#define getunique(v) {sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());}
using ll = int;
// using ll = int;
// #pragma warning("int")
//
using vl = vector<ll>;
using pl = pair<ll, ll>;
typedef long double ld;
typedef unsigned long long ull;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template <typename num_t>
using ordered_set = tree<num_t, null_type, less<num_t>, rb_tree_tag, tree_order_statistics_node_update>;
// const string PAIR_LEFT = "(";
// const string PAIR_RIGHT = ")";
// const string IT_LEFT = "[";
// const string IT_RIGHT = "]";
const string PAIR_LEFT = "{";
const string PAIR_RIGHT = "}";
const string IT_LEFT = "{";
const string IT_RIGHT = "}";
// benq - print any container + pair
template<typename T, typename = void> struct is_iterable : false_type {};
template<typename T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),decltype(end(declval<T>()))>> : true_type {};
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << PAIR_LEFT << p.f << ", " << p.s << PAIR_RIGHT; }
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v) {
cout << IT_LEFT;
for (auto it = v.begin(); it != v.end();) {
cout << *it;
if (++it != v.end()) cout << ", ";
}
return cout << IT_RIGHT;
}
template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) {
cin >> p.first;
return cin >> p.second;
}
template<typename T> void debug(string s, T x) {cerr << "\033[1;34m" << s << "\033[0;32m = \033[35m" << x << "\033[0m\n";}
template<typename T, typename... Args> void debug(string s, T x, Args... args) {for (int i=0, b=0; i<(int)s.size(); i++) if (s[i] == '(' || s[i] == '{') b++; else
if (s[i] == ')' || s[i] == '}') b--; else if (s[i] == ',' && b == 0) {cerr << "\033[1;34m" << s.substr(0, i) << "\033[0;32m = \033[35m" << x << "\033[31m | "; debug(s.substr(s.find_first_not_of(' ', i + 1)), args...); break;}}
template<typename T> void debug_nameless(T x) {cerr << "\033[35m" << x << "\033[0m\n";}
template<typename T, typename... Args> void debug_nameless(T x, Args... args) {cerr << "\033[35m" << x << "\033[31m | "; debug_nameless(args...);}
#ifdef galen_colin_local
#define pr(...) debug(#__VA_ARGS__, __VA_ARGS__)
#define prs(...) debug_nameless(__VA_ARGS__)
const bool local_ = true;
#else
#define pr(...) 135
#define prs(...) 135
const bool local_ = false;
#endif
mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
// mt19937_64 rng(61378913);
/* usage - just do rng() */
void usaco(string filename) {
// #pragma message("be careful, freopen may be wrong")
freopen((filename + ".in").c_str(), "r", stdin);
freopen((filename + ".out").c_str(), "w", stdout);
}
// #include <atcoder/all>
// using namespace atcoder;
// const ld pi = 3.14159265358979323846;
// const ll mod = 1000000007;
// const ll mod = 998244353;
// ll mod;
ll n, m, q, k, l, r, x, y, z;
const ll template_array_size = 1e6 + 206171;
ll a[template_array_size];
ll b[template_array_size];
ll c[template_array_size];
string s, t;
vl adj[100005];
vl ch[100005];
ll sz[100005];
ll top[100005];
vl at[100005];
ll lab[100005];
ll par[100005];
ll T = -1;
ll cl[100005];
ll path[100005][30];
ll psz[100005];
ll vis[100005];
ll ps[100005];
ll dsz(ll v, ll p) {
sz[v] = 1;
par[v] = p;
for (ll x: adj[v]) if (x != p) {
sz[v] += dsz(x, v);
ch[v].push_back(x);
}
return sz[v];
}
void dlab(ll v, ll p) {
lab[v] = ++T;
top[v] = v;
if (p != -1 && lab[p] + 1 == lab[v]) top[v] = top[p];
for (ll i = 1; i < ch[v].size(); i++) if (sz[ch[v][i]] > sz[ch[v][0]]) swap(ch[v][0], ch[v][i]);
for (ll x: ch[v]) dlab(x, v);
}
void dl(ll v, ll p) {
if (ch[v].size() == 0) cl[lab[v]] = 1;
for (ll x: ch[v]) {
dl(x, v);
cl[lab[v]] ^= cl[lab[x]];
}
}
inline ll gc(ll l, ll r, ll f) {
ll v = ps[r];
if (l > 0) v -= ps[l - 1];
if (!f) v = (r - l + 1) - v;
return v;
}
ll pc[100005][2];
inline ll gd(ll l, ll r, ll f) {
ll v = ps[r];
if (l > 0) v -= ps[l - 1];
if (!f) v = (r - l + 1) - v;
return 2 * v - (r - l + 1);
}
const bool run = local_ ? 0 : 1;
void solve(int tc = 0) {
cin >> n >> q;
for (ll i = 1; i < n; i++) {
cin >> x >> y;
--x; --y;
adj[x].push_back(y);
adj[y].push_back(x);
}
ll r = 0;
while (adj[r].size() == 1) ++r;
dsz(r, -1);
dlab(r, -1);
dl(r, -1);
for (ll i = 0; i < n; i++) {
ll t = i;
while (t != -1) {
path[i][psz[i]++] = t;
t = par[top[t]];
}
}
for (ll i = 0; i < n; i++) vis[i] = -1;
{
ll r = 0;
for (ll i = 0; i < n; i++) {
r += cl[i];
ps[i] = r;
}
}
for (ll i = 0; i < n; i++) {
ll t = lab[top[i]], l = lab[i];
for (ll j = 0; j < 2; j++) {
pc[l][j] = gd(t, l, j);
}
}
ll ra = n - 2 + gc(0, n - 1, 0);
for (ll i = 0; i < q; i++) {
cin >> m;
vl v(m);
for (ll &x: v) cin >> x, --x;
vl nv;
nv.reserve(m);
for (ll x: v) {
if (vis[x] != i && adj[x].size() == 1) {
vis[x] = i;
continue;
}
nv.push_back(x);
}
v = nv;
sort(v.begin(), v.end(), [&](ll a, ll b) {
return lab[a] < lab[b];
});
nv.clear();
for (ll x: v) {
if (nv.size() && nv.back() == x) nv.pop_back();
else nv.push_back(x);
}
v = nv;
for (ll x: v) {
for (ll i = 0; i < psz[x]; i++) {
ll y = path[x][i];
at[lab[top[y]]].push_back(lab[y]);
}
}
ll ans = ra + m;
for (ll x: v) {
for (ll i = 0; i < psz[x]; i++) {
ll y = path[x][i];
ll c = lab[top[y]];
if (at[c].size()) {
ll l = 0, r = at[c].size() - 1;
ll t = at[c].size() % 2;
while (l <= r) {
if (at[c][l] <= at[c][r]) {
ans += pc[at[c][l]][t];
++l;
} else {
ans += pc[at[c][r]][t];
--r;
}
t ^= 1;
}
at[c].clear();
}
}
}
if ((cl[lab[r]] + v.size()) % 2 == 1) {
cout << -1 << '\n';
} else {
cout << ans << '\n';
}
}
}
int main() {
#ifdef galen_colin_local
auto begin = std::chrono::high_resolution_clock::now();
#endif
send help
#ifndef galen_colin_local
// usaco("cbs");
#endif
// usaco("cowland");
// freopen("tc.txt", "r", stdin);
// freopen("tc.txt", "w", stdout);
// freopen("tc2.cpp", "w", stdout);
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
cout << setprecision(15) << fixed;
cerr << setprecision(4) << fixed;
int tc = 1;
// if (local_)
// if (!run)
// cin >> tc;
for (int t = 0; t < tc; t++) {
pr(t); prs(string(50, '-'));
solve(t);
prs(string(50, '-') + "\n");
}
#ifdef galen_colin_local
auto end = std::chrono::high_resolution_clock::now();
cerr << setprecision(4) << fixed;
cerr << "Execution time: " << std::chrono::duration_cast<std::chrono::duration<double>>(end - begin).count() << " seconds" << endl;
#endif
}
Compilation message
cleaning.cpp: In function 'void dlab(ll, ll)':
cleaning.cpp:141:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
141 | for (ll i = 1; i < ch[v].size(); i++) if (sz[ch[v][i]] > sz[ch[v][0]]) swap(ch[v][0], ch[v][i]);
| ~~^~~~~~~~~~~~~~
cleaning.cpp: In function 'int main()':
cleaning.cpp:76:17: warning: statement has no effect [-Wunused-value]
76 | #define pr(...) 135
| ^~~
cleaning.cpp:315:9: note: in expansion of macro 'pr'
315 | pr(t); prs(string(50, '-'));
| ^~
cleaning.cpp:77:18: warning: statement has no effect [-Wunused-value]
77 | #define prs(...) 135
| ^~~
cleaning.cpp:315:16: note: in expansion of macro 'prs'
315 | pr(t); prs(string(50, '-'));
| ^~~
cleaning.cpp:77:18: warning: statement has no effect [-Wunused-value]
77 | #define prs(...) 135
| ^~~
cleaning.cpp:317:9: note: in expansion of macro 'prs'
317 | prs(string(50, '-') + "\n");
| ^~~
cleaning.cpp: In function 'void usaco(std::string)':
cleaning.cpp:87:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
87 | freopen((filename + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cleaning.cpp:88:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
88 | freopen((filename + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
10588 KB |
Output is correct |
| 2 |
Correct |
25 ms |
16748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
13884 KB |
Output is correct |
| 2 |
Correct |
13 ms |
13916 KB |
Output is correct |
| 3 |
Correct |
27 ms |
27248 KB |
Output is correct |
| 4 |
Correct |
30 ms |
24352 KB |
Output is correct |
| 5 |
Correct |
38 ms |
28236 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
14428 KB |
Output is correct |
| 2 |
Correct |
14 ms |
14496 KB |
Output is correct |
| 3 |
Correct |
48 ms |
38484 KB |
Output is correct |
| 4 |
Correct |
64 ms |
38088 KB |
Output is correct |
| 5 |
Correct |
35 ms |
36948 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
17496 KB |
Output is correct |
| 2 |
Correct |
13 ms |
16476 KB |
Output is correct |
| 3 |
Correct |
13 ms |
16476 KB |
Output is correct |
| 4 |
Correct |
10 ms |
17244 KB |
Output is correct |
| 5 |
Correct |
10 ms |
17336 KB |
Output is correct |
| 6 |
Correct |
16 ms |
17244 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
58 ms |
24180 KB |
Output is correct |
| 2 |
Correct |
50 ms |
23888 KB |
Output is correct |
| 3 |
Correct |
31 ms |
17500 KB |
Output is correct |
| 4 |
Correct |
50 ms |
24028 KB |
Output is correct |
| 5 |
Correct |
48 ms |
23900 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
95 ms |
29012 KB |
Output is correct |
| 2 |
Correct |
74 ms |
31600 KB |
Output is correct |
| 3 |
Correct |
83 ms |
32852 KB |
Output is correct |
| 4 |
Correct |
83 ms |
32140 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
10588 KB |
Output is correct |
| 2 |
Correct |
25 ms |
16748 KB |
Output is correct |
| 3 |
Correct |
13 ms |
13884 KB |
Output is correct |
| 4 |
Correct |
13 ms |
13916 KB |
Output is correct |
| 5 |
Correct |
27 ms |
27248 KB |
Output is correct |
| 6 |
Correct |
30 ms |
24352 KB |
Output is correct |
| 7 |
Correct |
38 ms |
28236 KB |
Output is correct |
| 8 |
Correct |
13 ms |
14428 KB |
Output is correct |
| 9 |
Correct |
14 ms |
14496 KB |
Output is correct |
| 10 |
Correct |
48 ms |
38484 KB |
Output is correct |
| 11 |
Correct |
64 ms |
38088 KB |
Output is correct |
| 12 |
Correct |
35 ms |
36948 KB |
Output is correct |
| 13 |
Correct |
21 ms |
17496 KB |
Output is correct |
| 14 |
Correct |
13 ms |
16476 KB |
Output is correct |
| 15 |
Correct |
13 ms |
16476 KB |
Output is correct |
| 16 |
Correct |
10 ms |
17244 KB |
Output is correct |
| 17 |
Correct |
10 ms |
17336 KB |
Output is correct |
| 18 |
Correct |
16 ms |
17244 KB |
Output is correct |
| 19 |
Correct |
58 ms |
24180 KB |
Output is correct |
| 20 |
Correct |
50 ms |
23888 KB |
Output is correct |
| 21 |
Correct |
31 ms |
17500 KB |
Output is correct |
| 22 |
Correct |
50 ms |
24028 KB |
Output is correct |
| 23 |
Correct |
48 ms |
23900 KB |
Output is correct |
| 24 |
Correct |
95 ms |
29012 KB |
Output is correct |
| 25 |
Correct |
74 ms |
31600 KB |
Output is correct |
| 26 |
Correct |
83 ms |
32852 KB |
Output is correct |
| 27 |
Correct |
83 ms |
32140 KB |
Output is correct |
| 28 |
Correct |
45 ms |
23644 KB |
Output is correct |
| 29 |
Correct |
62 ms |
32424 KB |
Output is correct |
| 30 |
Correct |
37 ms |
28236 KB |
Output is correct |
| 31 |
Correct |
51 ms |
37972 KB |
Output is correct |
| 32 |
Correct |
54 ms |
23888 KB |
Output is correct |
| 33 |
Correct |
66 ms |
30580 KB |
Output is correct |
| 34 |
Correct |
72 ms |
32852 KB |
Output is correct |
| 35 |
Correct |
63 ms |
32596 KB |
Output is correct |
