QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#108208 | #6103. A+B Problem | foreverlose | TL | 0ms | 0kb | C++14 | 1.7kb | 2023-05-23 21:33:22 | 2023-05-23 21:35:46 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, x, y) for(int i = (x), stOxrj = (y); i <= stOxrj; ++i)
#define irep(i, x, y) for(int i = (x), stOxrj = (y); i >= stOxrj; --i)
#define pb emplace_back
#define all(S) S.begin(), S.end()
#define fi first
#define se second
#define il inline
#define let const auto
using pii = pair<int, int>;
using vint = vector<int>;
template<typename T>
il void tmax(T &x, const T &y) { if(x < y) x = y; }
template<typename T>
il void tmin(T &x, const T &y) { if(x > y) x = y; }
il int read() {
int res = 0, flag = 1; char c = getchar();
while(c < '0' || c > '9') { if(c == '-') flag = -1; c = getchar(); }
while(c >= '0' && c <= '9') res = res * 10 + c - '0', c = getchar();
return res * flag;
}
const int N = 2.5e5 + 200;
int fa[N];
int findf(int x) { return fa[x] == x ? x : fa[x] = findf(fa[x]); }
int faz[N];
vint G[N];
void dfs(int u, int fat) {
faz[u] = fat;
for(int v : G[u]) if(v != fat) dfs(v, u);
}
int sz[N];
bool vs[N];
signed main() {
// freopen("1.in", "r", stdin);
int n = read();
rep(i, 2, n) {
int u = read(), v = read();
G[u].pb(v), G[v].pb(u);
}
dfs(1, 0);
rep(i, 1, n) fa[i] = i;
int Q = read();
while(Q--) {
int k = read();
vint vec(k);
for(int &x : vec) x = read(), vs[x] = true;
for(int x : vec) if(vs[faz[x]]) fa[x] = findf(faz[x]);
for(int x : vec) sz[findf(x)]++;
ll ans = 0;
for(int x : vec) if(findf(x) == x) ans += 1ll * sz[x] * (sz[x] - 1) / 2;
cout << ans << '\n';
for(int x : vec) fa[x] = x, vs[x] = false, sz[x] = 0;
}
return 0;
}
詳細信息
Test #1:
score: 0
Time Limit Exceeded
input:
4 1 1 1