给定
属实是一道水题,最开始还在想有什么性质,比如是不是最多是一棵二叉树之类的。。。然后突然发现保证了 vis
和注意别漏了
xxxxxxxxxx
831
2
3
4
5
6
7
8
9
10
11using namespace std;
12
13mt19937 rnd(random_device{}());
14int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15bool rnddd(int x){return rndd(1, 100) <= x;}
16
17typedef unsigned int uint;
18typedef unsigned long long unll;
19typedef long long ll;
20typedef long double ld;
21
22template < typename T = int >
23inline T read(void);
24
25struct Edge{
26 Edge* nxt;
27 int to;
28 OPNEW;
29}ed[610000];
30ROPNEW(ed);
31Edge* head[160000];
32
33int N, M;
34bitset < 160000 > vis;
35
36int bfs(int S, int D){
37 if(!D)return S;
38 basic_string < int > nods;
39 queue < pair < int, int > > cur;
40 cur.push({S, 0}), vis[S] = true, nods += S;
41 while(!cur.empty()){
42 auto tp = cur.front(); cur.pop();
43 for(auto i = head[tp.first]; i; i = i->nxt)
44 if(!vis[SON]){
45 vis[SON] = true;
46 nods += SON;
47 if(tp.second + 1 < D)cur.push({SON, tp.second + 1});
48 }
49 }int ret(0);
50 for(auto nod : nods)vis[nod] = false, ret += nod;
51 return ret;
52}
53
54int main(){
55 N = read(), M = read();
56 for(int i = 1; i <= M; ++i){
57 int s = read(), t = read();
58 head[s] = new Edge{head[s], t};
59 head[t] = new Edge{head[t], s};
60 }int Q = read();
61 while(Q--){
62 int S = read(), D = read();
63 printf("%d\n", bfs(S, D));
64 }
65 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
66 return 0;
67}
68
69template < typename T >
70inline T read(void){
71 T ret(0);
72 int flag(1);
73 char c = getchar();
74 while(c != '-' && !isdigit(c))c = getchar();
75 if(c == '-')flag = -1, c = getchar();
76 while(isdigit(c)){
77 ret *= 10;
78 ret += int(c - '0');
79 c = getchar();
80 }
81 ret *= flag;
82 return ret;
83}
update-2022_12_06 初稿