QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#624530 | #6102. Query on a Tree | DreamAwaking | RE | 91ms | 14372kb | C++14 | 2.1kb | 2024-10-09 16:02:21 | 2024-10-09 16:02:22 |
Judging History
answer
#include <bits/stdc++.h>
#define db(x) cerr<<#x<<" "<<(x)<<"\n"
#define db1(x) cerr<<#x<<" "<<(x)<<" "
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define ll long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
using pii = pair<int,int>;
const int N = 2e5+10;
int n,m,q,k,f,fa[N],siz[N],par[N],tmp[N];
int vis[N];
ll ans;
vector<int> v[N];
void dfs(int x,int f){
par[x] =f;
for(auto y:v[x]){
if(y==f)continue;
dfs(y,x);
}
}
int find(int x){
return x==fa[x]?x:fa[x] =find(fa[x]);
}
ll f1(int x){
return 1ll*x*(x-1)/2;
}
void Union(int x,int y){
x = find(x),y = find(y);
if(x==y)return ;
fa[x] = y;
// if(siz[x]>siz[y])swap(x,y);
// fa[x] = y;
// ans-=f1(siz[x])+f1(siz[y]);
// siz[y]+=siz[x];
// ans+=f1(siz[y]);
}
void solve()
{
cin>>n;
for(int i=1;i<n;i++){
int x,y;cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1,-1);
cin>>q;
for(int i=1;i<=n;i++)fa[i] =i,siz[i] =1;
for(int t =1;t<=q;t++){
ans =0;
cin>>k;
for(int i=1;i<=k;i++){
int x;cin>>x;tmp[i] =x;vis[x] =1;
}
for(int i=1;i<=k;i++){
int x = tmp[i],y = par[x];
if(y==-1||!vis[y])continue;
Union(x,y);
}
for(int i=1;i<=k;i++){
vis[tmp[i]] =0;
}
for(int i=1;i<=k;i++){
vis[find(tmp[i])]++;
}
for(int i=1;i<=k;i++){
int x =tmp[i];
if(find(x)==x)ans+=f1(vis[x]);
}
cout<<ans<<"\n";
//cout<<"ans = "<<ans<<"\n";
// map<int,int> mp;
// for(int i=1;i<=k;i++){
// mp[find(tmp[i])]++;
// }
// // ans =0;
// // cout<<" t = "<<t<<"\n";
// for(auto [x,num]:mp){
// //ans+=num*(num-1)/2;
// // cout<<"x = "<<x<<" num ="<<num<<"\n";
// }
for(int i=1;i<=k;i++){
int x = tmp[i];
vis[tmp[i]] =0;
fa[tmp[i]] = tmp[i],siz[tmp[i]] = 1;
}
// for(int i=1;i<=n;i++)db1(fa[i]);db(1);
// for(int i=1;i<=n;i++)db1(siz[i]);db(1);
// for(int i=1;i<=n;i++){
// if(fa[i]!=i)cout<<"NP\n";
// }
// cout<<ans<<"\n";
}
return ;
}
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int _=1;
while(_--)solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 11668kb
input:
7 1 2 1 3 1 5 2 7 4 6 4 7 6 1 1 2 1 2 4 1 2 3 4 5 1 2 4 6 7 6 1 2 3 4 5 6 7 1 2 3 4 5 6 7
output:
0 1 3 10 7 21
result:
ok 6 numbers
Test #2:
score: 0
Accepted
time: 0ms
memory: 11048kb
input:
3 1 3 2 1 1000 3 1 3 2 3 2 3 1 3 1 3 2 3 3 2 1 2 2 1 2 2 1 2 2 3 3 3 2 1 2 1 2 2 1 2 2 3 1 3 3 2 1 3 3 2 1 3 3 2 1 2 1 2 2 3 2 2 2 3 2 3 1 2 1 2 2 2 1 3 3 1 2 3 1 2 3 3 2 3 1 2 1 3 3 2 3 1 3 1 3 2 2 2 1 2 2 3 2 2 3 2 2 3 2 1 3 2 1 3 2 3 2 2 1 3 3 1 2 3 3 2 1 3 2 3 2 2 1 3 3 2 1 3 2 2 1 2 2 1 3 3 2 1...
output:
3 3 3 3 1 1 0 3 1 1 1 3 3 3 1 0 0 1 1 1 3 3 3 1 3 3 1 0 0 0 1 1 0 1 3 3 0 1 3 1 1 3 1 1 3 3 1 0 3 3 3 1 1 3 3 1 3 1 3 0 1 1 3 0 3 1 3 3 1 3 1 3 1 1 0 0 0 0 1 0 1 3 3 0 3 1 3 3 1 3 3 3 1 1 1 3 3 1 3 0 1 1 3 3 0 1 3 1 1 1 3 0 3 0 3 3 3 3 3 0 3 3 3 0 3 3 3 3 3 1 1 0 3 1 1 1 1 1 3 1 3 0 1 0 0 1 3 3 3 1 ...
result:
ok 1000 numbers
Test #3:
score: 0
Accepted
time: 4ms
memory: 12212kb
input:
3 1 3 2 3 10000 3 2 3 1 3 1 2 3 2 2 1 3 3 2 1 3 2 3 1 3 2 3 1 3 2 3 1 3 2 1 3 2 3 1 2 3 1 3 1 2 3 2 2 3 2 2 1 2 2 3 2 2 3 2 2 3 3 3 1 2 2 1 3 2 3 1 3 3 2 1 3 1 2 3 2 1 3 2 2 1 2 2 3 3 3 2 1 2 2 3 3 2 3 1 3 1 3 2 3 2 3 1 2 2 1 2 2 1 3 3 2 1 2 1 2 3 3 2 1 2 1 2 3 3 1 2 3 3 2 1 2 3 1 3 3 2 1 3 2 3 1 2 ...
output:
3 3 0 3 3 3 3 3 1 1 3 1 0 1 1 1 3 1 1 3 3 1 0 1 3 1 3 3 3 0 0 3 0 3 0 3 3 1 3 3 1 0 0 3 1 3 3 3 3 1 1 3 1 0 3 0 1 1 0 3 1 3 3 1 3 0 0 0 3 3 1 1 1 0 3 3 3 1 0 1 3 0 3 1 3 0 3 3 3 3 3 3 3 1 1 3 3 0 1 3 3 1 3 0 1 1 3 3 3 3 3 1 1 0 3 3 3 1 1 0 0 0 1 0 3 1 1 3 1 0 3 1 3 0 3 3 3 0 3 3 0 3 1 3 3 3 3 3 3 1 ...
result:
ok 10000 numbers
Test #4:
score: 0
Accepted
time: 19ms
memory: 10844kb
input:
3 3 1 2 3 100000 2 3 1 2 2 3 3 1 3 2 3 1 2 3 2 2 3 2 1 2 2 2 1 3 2 3 1 3 2 3 1 3 2 1 3 3 1 3 2 3 1 3 2 3 2 1 3 2 2 1 3 1 2 3 2 3 2 3 2 1 3 3 1 3 2 2 3 1 3 3 2 1 2 1 2 2 2 1 3 2 1 3 2 2 1 3 2 1 3 2 1 3 3 1 3 2 2 2 3 2 3 1 2 2 1 2 1 3 3 1 3 2 3 1 2 3 3 3 1 2 2 3 2 3 2 3 1 2 3 1 3 1 2 3 2 3 1 2 2 1 3 1...
output:
1 1 3 3 1 0 0 3 3 3 3 3 3 0 3 1 3 3 1 3 0 0 3 0 3 1 3 1 1 0 1 3 3 3 1 3 1 3 1 0 3 1 1 3 0 0 1 3 1 3 0 1 1 0 3 1 0 3 3 1 1 3 3 3 0 3 3 1 1 3 1 3 3 3 3 1 3 1 3 3 3 0 0 0 1 0 0 3 1 1 3 0 1 1 3 1 1 3 0 3 3 3 1 3 1 3 3 1 3 1 3 1 3 1 3 1 1 3 3 3 0 3 3 1 3 3 1 1 3 3 1 3 3 1 0 3 3 3 1 0 3 1 1 0 3 3 3 1 3 3 ...
result:
ok 100000 numbers
Test #5:
score: 0
Accepted
time: 0ms
memory: 11920kb
input:
13 4 7 8 2 5 11 5 9 3 11 1 2 11 10 6 7 7 1 6 12 4 11 13 12 27 13 11 5 8 10 13 2 9 4 6 12 1 3 7 10 9 5 4 3 11 2 13 8 7 10 8 1 12 13 9 6 5 10 11 11 2 8 13 10 7 9 3 4 1 11 12 9 8 3 9 13 11 6 1 10 4 8 3 4 8 5 10 6 7 13 10 11 12 5 4 1 7 3 2 10 9 10 10 4 11 2 5 13 6 7 8 3 9 6 1 11 8 2 5 9 13 12 10 4 8 9 6...
output:
78 22 9 29 6 3 36 22 9 45 36 5 7 16 16 46 4 8 78 66 78 45 46 45 13 11 11
result:
ok 27 numbers
Test #6:
score: 0
Accepted
time: 2ms
memory: 11856kb
input:
50 37 5 5 8 2 46 39 21 19 35 39 3 46 33 8 16 14 13 12 39 24 18 9 20 10 12 22 12 41 25 25 42 34 41 20 17 44 6 39 17 25 37 31 26 22 42 6 12 13 16 4 5 32 7 16 36 50 31 42 33 40 11 6 50 32 15 12 24 31 49 39 1 46 15 7 43 48 21 7 11 30 38 30 16 23 6 5 45 19 18 27 6 38 47 27 29 32 28 50 37 10 11 17 15 43 1...
output:
130 634 425 95 991 1081 265 98 562 574 204 329 222 990 400 1225 1225 43 254 777 195 1081 255 1035 89 918 1225 177 531 86 841 238 110 1036 1225 334 867 67 451 126 106 71 156 118 443 104 96 66 218 29
result:
ok 50 numbers
Test #7:
score: 0
Accepted
time: 3ms
memory: 11700kb
input:
50 15 50 5 28 5 15 15 13 28 17 28 43 41 12 23 33 29 13 34 42 22 46 19 41 35 23 8 3 40 21 37 23 33 25 24 35 26 28 18 6 16 30 11 25 17 2 27 20 17 7 33 48 19 32 31 11 10 26 45 24 31 49 41 2 39 40 10 33 45 38 33 18 16 14 41 44 33 3 39 11 20 15 5 30 22 20 9 27 31 36 24 34 4 12 47 42 1 4 50 33 22 49 21 7 ...
output:
129 114 408 296 56 706 239 242 1225 279 269 990 84 124 411 185 60 129 132 128 481 51 155 63 192 116 162 742 136 992 659 38 191 73 204 709 225 134 862 490 787 90 146 407 1225 259 946 359 93 276
result:
ok 50 numbers
Test #8:
score: 0
Accepted
time: 0ms
memory: 11024kb
input:
50 39 2 9 5 9 42 48 47 34 50 22 37 27 3 1 25 7 36 13 31 28 25 24 40 2 34 20 23 16 41 24 10 42 26 3 6 18 42 1 39 50 13 29 42 3 41 31 5 22 14 9 14 2 3 14 7 20 39 41 38 30 48 4 1 43 21 1 15 30 10 41 12 29 40 40 17 49 5 30 35 46 41 6 43 7 45 48 19 33 49 22 44 8 15 42 32 39 11 50 49 50 9 2 17 4 10 12 6 2...
output:
532 309 1225 490 1176 1225 89 45 406 903 168 151 332 112 1035 122 223 861 1081 1035 324 290 946 251 190 990 1225 153 238 1225 1128 109 199 302 148 240 1225 160 467 867 253 504 129 82 946 359 147 82 905 381
result:
ok 50 numbers
Test #9:
score: 0
Accepted
time: 54ms
memory: 11128kb
input:
2125 1692 784 76 63 37 1633 736 46 1644 1621 893 1413 1100 671 318 150 1207 30 777 1693 569 2061 2090 1731 487 1766 1749 1094 1128 1860 564 486 405 1842 848 977 1357 832 571 1378 1638 1064 423 132 251 1118 367 965 328 351 102 433 2088 763 353 962 857 2046 944 105 1337 683 123 372 1306 1409 424 2026 ...
output:
1186 3088 3 45801 24 6 1 2 16666 50392 8028 24 248782 97903 115 26304 50656 34 11398 977 1414 1654 113418 1313623 45 83432 650584 78767 6633 1405 249 35778 7123 248 227 2 52228 14433 2024749 6765 12634 1353 2158 14498 252 14064 365 914 190 5757 17 57 10345 12731 2424 2773 1280269 238371 42821 6337 3...
result:
ok 687 numbers
Test #10:
score: 0
Accepted
time: 63ms
memory: 10964kb
input:
2500 1397 89 1576 1217 892 95 783 1361 1399 651 696 319 1067 622 149 318 275 748 1950 251 2085 1593 714 930 2462 2494 1352 1531 2187 866 1238 789 480 2373 1658 1906 2013 853 1279 2212 1584 2284 1345 1578 33 478 1786 485 2182 1157 2438 63 695 1124 792 628 375 2188 134 2064 1909 1963 1562 566 1932 220...
output:
271791 10323 4881 0 0 292793 0 0 14323 0 0 297 0 0 0 0 0 0 1 0 5890 0 17889 0 0 0 3657 16 348 338 0 0 0 0 0 0 0 0 0 0 0 54123 0 0 1 0 49 0 0 0 0 5681 223 0 0 0 11 309 0 0 0 0 103699 0 0 0 0 301408 1 0 0 0 0 0 0 0 0 0 51966 0 0 0 0 0 21334 0 4858 3684 0 18 1304 0 0 0 1071 0 0 1 0 329 0 0 0 0 0 0 0 69...
result:
ok 2500 numbers
Test #11:
score: 0
Accepted
time: 63ms
memory: 11708kb
input:
2500 2321 1434 2130 898 145 1168 470 145 555 37 1136 267 1157 1851 472 735 701 806 2469 1992 834 1871 723 1801 1523 202 369 1187 2307 328 2156 1263 876 806 1062 2314 1947 927 1017 427 2081 1206 2329 1236 1530 1562 1098 2025 300 1520 551 1819 1084 549 1392 1374 1558 1513 181 2368 612 1569 897 344 146...
output:
0 0 0 0 0 2047 0 0 17016 27023 0 1046 7951 0 46 0 7805 38643 0 1064 0 0 6027 0 0 0 0 0 57 25321 0 0 0 0 0 0 0 0 0 1354 298011 0 0 0 317649 92 230 30101 0 0 0 0 4079 0 0 198 0 0 213837 0 0 0 0 0 0 0 0 705 485 0 0 0 0 0 0 2575 0 25624 4228 0 0 0 0 0 0 0 104 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7715 103881 ...
result:
ok 2500 numbers
Test #12:
score: 0
Accepted
time: 63ms
memory: 11408kb
input:
2500 746 278 2080 2068 3 2444 1646 1837 2210 1719 1779 614 2056 1592 2487 1152 116 261 487 2449 2286 457 732 1184 2072 614 2294 1252 1620 198 1178 2137 667 250 875 222 1473 2490 958 537 682 1821 1418 690 2422 350 205 1269 1522 2283 1369 2359 1073 2073 2392 1109 649 634 1036 173 1815 2390 436 122 119...
output:
0 0 0 1 0 5 0 0 0 0 1082 0 0 0 0 0 1 0 0 0 0 372 0 0 1571 0 0 22336 0 650 35049 0 6154 56 0 0 5402 0 0 10493 0 0 15 0 0 455 563527 0 9697 0 261 0 0 0 0 0 16772 0 0 0 17 938 226069 33878 0 0 0 253 0 1026 0 0 0 0 0 0 0 0 0 1843 0 0 0 0 466 37564 0 0 66 0 0 0 1 0 69 332 471 0 2215 0 0 0 0 27160 0 0 210...
result:
ok 2500 numbers
Test #13:
score: 0
Accepted
time: 59ms
memory: 12260kb
input:
2500 1874 1418 133 1750 1756 209 1129 825 1570 902 2015 358 2350 526 310 1569 338 319 1209 1690 1035 939 1346 363 1133 823 1515 305 1740 877 405 2408 254 978 484 2322 1406 269 492 444 975 2231 2199 145 611 1433 2221 309 2140 145 1779 1615 1667 893 84 843 2239 1447 1687 1489 1531 1995 2067 708 729 28...
output:
591 0 0 0 118 0 0 0 0 0 139031 0 20316 0 397 0 0 0 0 54 0 0 0 0 0 18749 755186 0 0 0 502 0 0 33 515 0 0 0 645343 0 3389 1536 0 0 0 0 0 0 0 0 55 0 0 0 0 0 0 24 0 0 18781 0 0 0 3605 0 0 4905 1 0 0 1057 0 0 0 4403 0 0 13858 0 0 1183 0 180 0 0 3463 36165 1865 0 0 73120 0 0 0 31150 0 0 0 0 0 0 0 0 0 0 58...
result:
ok 2500 numbers
Test #14:
score: 0
Accepted
time: 59ms
memory: 12120kb
input:
2500 298 263 2379 1227 1818 1486 612 2313 929 84 159 2398 2440 267 2325 1986 561 2273 1727 1134 1475 1012 1355 2246 194 1839 533 166 1052 747 1323 986 853 2115 1989 26 1136 344 230 1363 2279 1153 684 2303 2108 221 2136 1849 54 908 905 667 1452 522 480 781 1126 568 1938 1793 438 316 2414 486 464 1649...
output:
0 5427 0 0 0 0 0 0 0 0 0 0 0 4372 0 2003 0 0 485 0 0 0 0 0 0 0 212 0 0 0 0 0 0 0 0 597 0 0 0 3674 152 0 0 1302 1827 1 0 0 0 0 0 0 5561 0 0 0 0 0 0 15125 0 0 0 0 0 0 0 5 0 0 1203 0 1250 14230 0 0 0 0 0 0 0 0 0 1307 1744 8639 0 0 203690 0 0 0 0 66468 0 101386 147201 6402 0 0 0 518 0 0 0 0 0 0 0 0 1142...
result:
ok 2500 numbers
Test #15:
score: 0
Accepted
time: 91ms
memory: 14372kb
input:
98246 3650 41804 33441 91212 31858 45777 26280 1021 42752 11638 69613 11500 24634 34071 92610 60294 8935 87882 86958 14022 51707 53093 90392 66077 9263 41911 41042 5636 26146 40921 72138 89357 10979 5882 80910 93086 75618 66667 94037 20575 83310 29226 82200 75277 22984 72723 14257 19092 74647 97034 ...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 9843 numbers
Test #16:
score: -100
Runtime Error
input:
250000 214553 54714 71256 226500 127178 173505 85122 145888 186314 141085 76547 28443 149456 30947 12037 20860 120859 145004 123686 189726 115672 191621 176791 242640 204589 240143 172080 55269 49042 25311 163578 145461 226899 91039 47491 75338 155567 1692 32558 240020 185020 134550 154352 61766 173...