QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#108208#6103. A+B ProblemforeverloseTL 0ms0kbC++141.7kb2023-05-23 21:33:222023-05-23 21:35:46

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-23 21:35:46]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2023-05-23 21:33:22]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

4
1
1
1

output:


result: