QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#708507 | #3000. 希望 | TheZone | 100 ✓ | 1030ms | 432936kb | C++20 | 8.3kb | 2024-11-03 23:03:22 | 2024-11-03 23:03:23 |
Judging History
answer
#include <iostream>
#include <cassert>
#include <vector>
#include <tuple>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define ssz(x) (int((x).size()))
auto chmax = [](auto& x, auto y) { if (x < y) x = y; };
auto chmin = [](auto& x, auto y) { if (y < x) x = y; };
using ll = long long;
const int N = 1e6, mod = 998244353;
struct info{
int mu, imu, ad, zs;
}
tf[N], tf2[N];
int hd[N], des[N * 2], nxt[N * 2], ff[N], f[N], f2[N], g[N], st[N], ed[N], mxd[N], fac[N + 1], ifac[N + 1], ec = 0, ind = 0;
vector<pair<int, int>> buc[N];
vector<pair<int, int>> stk[N], fs[N];
vector<int> tr[N];
void add(int s, int t){
des[ec] = t;
nxt[ec] = hd[s];
hd[s] = ec++;
}
void dfs0(int id, int fa){
mxd[id] = ff[id] = 1;
for (int p = hd[id], dst; p != -1; p = nxt[p]){
dst = des[p];
if (dst != fa){
dfs0(dst, id);
buc[mxd[dst]].emplace_back(id, dst);
chmax(mxd[id], mxd[dst] + 1);
ff[id] = 1ll * ff[id] * ff[dst] % mod;
}
}
ff[id] = (ff[id] + 1) % mod;
}
ll qpow(ll bs, ll ix){
ll mul = bs, ret = 1;
while (ix){
if (ix & 1)
ret = (ret * mul) % mod;
mul = (mul * mul) % mod;
ix >>= 1;
}
return ret;
}
int recvg(int x, int i, const info& t) {
return ((i >= t.zs ? 0 : 1ll * t.mu * x) + t.ad) % mod;
}
int recvf(int x, int i, const info& t) {
return ((i < t.zs ? 0 : 1ll * t.mu * x) + t.ad) % mod;
}
int recv(int x, int i) {
return recvf(fs[x][i].first, i, tf[x]);
}
void mergef(int id, int x, int lsf, int ilsf){
if (lsf)
tf[id].imu = 1ll * tf[id].imu * ilsf % mod;
for (int i = ssz(fs[x]) - 1, j = ssz(fs[id]) - 1; i >= 0; i--, j--){
int cv = 1ll * recv(x, i) * recv(id, j) % mod;
fs[id][j].first = 1ll * (cv - 1ll * tf[id].ad * lsf % mod + mod) * tf[id].imu % mod;
}
tf[id].ad = 1ll * tf[id].ad * lsf % mod;
if (lsf)
tf[id].mu = 1ll * tf[id].mu * lsf % mod;
else{
int dv = ssz(fs[id]) - ssz(fs[x]);
for (int i = dv; i < ssz(fs[id]); i++)
fs[id][i].first = recv(id, i);
tf[id] = { 1, 1, 0, dv };
}
}
int l;
void dfs1(int id){
tf[id] = { 1, 1, 0, 0 };
// cerr << id << endl;
st[id] = ind++;
for (auto x : tr[id])
{
// cerr << x << " " << id << endl;
dfs1(x);
if (fs[id].empty())
{
swap(fs[x], fs[id]);
tf[id] = tf2[x] = tf[x];
continue;
}
mergef(id, x, ff[x], 1ll * ifac[x + 1] * fac[x] % mod);
int dv = ssz(fs[id]) - ssz(fs[x]);
for (int i = dv; i < ssz(fs[id]); i++)
stk[fs[id][i].second].emplace_back(fs[id][i].first, st[x]);
tf2[x] = tf[id];
}
int ev = 1ll * (1 - tf[id].ad + mod) * tf[id].imu % mod;
fs[id].emplace_back(ev, id);
stk[id].emplace_back(ev, st[id]);
(tf[id].ad += 1) %= mod;
f[id] = recv(id, ssz(fs[id]) - 1 - min(mxd[id] - 1, l));
if (l > 0)
f2[id] = recv(id, ssz(fs[id]) - 1 - min(mxd[id] - 1, l - 1));
ed[id] = ind;
}
void dfs2(int id, vector<pair<int, int>>& gs, info tg)
{
assert(ssz(gs) == mxd[id]);
g[id] = recvg(gs.back().first, ssz(gs) - 1, tg);
gs.pop_back();
if (gs.empty())
return;
int lsf = 1, ilsf = 1;
for (int i = ssz(tr[id]) - 1; i > 0; i--)
{
int x = tr[id][i];
vector<pair<int, int>> ngs(mxd[x]);
for (int y = x, j = ssz(ngs) - 1, k = ssz(gs) - 1; y != -1; y = tr[y].empty() ? -1 : tr[y][0], j--, k--)
{
ngs[j] = { recvg(gs[k].first, k, tg), y };
// cerr << id << " " << j << " " << recvg(gs[k].first, k, tg) << endl;
}
if (i < ssz(tr[id]) - 1)
{
int y = tr[id][i + 1];
for (int j = ssz(fs[y]) - l + 1, k = ssz(ngs) - 1; k >= 0 && j < ssz(fs[y]); j++, k--)
{
ngs[k].first = 1ll * ngs[k].first * recv(y, max(0, j)) % mod;
// cerr << id << " " << k << " " << recv(y, max(0, j)) << endl;
}
}
int y = tr[id][i - 1];
// cerr << id << " " << x << " " << y << endl;
for (int j = max(0, ssz(ngs) - l + 1); j < ssz(ngs); j++)
{
int k = max(0, ssz(gs) - (l - (ssz(ngs) - j))), p = gs[k].second;
// cerr << p << " " << ssz(stk[p]) << endl;
while (!stk[p].empty() && stk[p].back().second >= ed[y])
stk[p].pop_back();
assert(!stk[p].empty());
int &v = ngs[j].first;
v = 1ll * v * recvf(stk[p].back().first, k, tf2[y]) % mod;
// cerr << id << " " << j << " " << recvf(stk[p].back().first, k, tf2[y]) << endl;
}
if (ssz(ngs) >= l)
end(ngs)[-l].first = 1;
dfs2(x, ngs, { 1, 1, 1, ssz(ngs) });
if (i < ssz(tr[id]) - 1)
{
int y = tr[id][i + 1];
mergef(x, y, lsf, ilsf);
}
lsf = 1ll * lsf * ff[x] % mod, ilsf = 1ll * ilsf * ifac[x + 1] % mod * fac[x] % mod;
}
if (ssz(tr[id]) > 1)
{
int y = tr[id][1];
// cerr << lsf << " " << ilsf << " " << 1ll * lsf * ilsf % mod << endl;
if (lsf)
tg.imu = 1ll * tg.imu * ilsf % mod;
// cerr << ssz(gs) << " " << ssz(fs[y]) << endl;
for (int j = 0, k = ssz(gs) - (l - ssz(fs[y])); k >= 0 && j < ssz(fs[y]); j++, k--)
if (k < ssz(gs))
{
// cerr << id << " " << k << " " << recvg(gs[k].first, k, tg) << " " << recv(y, j) << endl;
int cv = 1ll * recvg(gs[k].first, k, tg) * recv(y, j) % mod;
gs[k].first = 1ll * (cv - 1ll * tg.ad * lsf % mod + mod) * tg.imu % mod;
// cerr << gs[k].first << " " << recvg(gs[k].first, k, tg) << endl;
}
// cerr << gs.back().first << " " << recvg(gs.back().first, ssz(gs) - 1, tg) << endl;
tg.ad = 1ll * tg.ad * lsf % mod;
if (lsf)
tg.mu = 1ll * tg.mu * lsf % mod;
else
{
// cerr << "? " << ssz(fs[y]) << " " << ssz(gs) << endl;
int dv = ssz(gs) + ssz(fs[y]) - l;
for (int i = max(0, ssz(gs) - l + 1); i < dv && i < ssz(gs); i++)
gs[i].first = recvg(gs[i].first, i, tg);
tg = { 1, 1, 0, dv };
}
}
if (ssz(gs) >= l)
end(gs)[-l].first = 1ll * (1 - tg.ad + mod) * tg.imu % mod;
(tg.ad += 1) %= mod;
// cerr << gs.back().first << " " << recvg(gs.back().first, ssz(gs) - 1, tg) << endl;
dfs2(tr[id][0], gs, tg);
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> l >> k;
fill(hd, hd + n, -1);
for (int i = 1, x, y; i < n; i++)
{
cin >> x >> y, x--, y--;
add(x, y), add(y, x);
}
dfs0(0, -1);
for (int i = n - 1; i >= 0; i--)
for (auto [p, x] : buc[i])
{
// cerr << p << " --> " << x << endl;
tr[p].emplace_back(x);
}
fac[0] = 1;
for (int i = 0; i < n; i++)
fac[i + 1] = 1ll * fac[i] * (ff[i] ? ff[i] : 1) % mod;
ifac[n] = qpow(fac[n], mod - 2);
for (int i = n; i > 0; i--)
ifac[i - 1] = 1ll * ifac[i] * (ff[i - 1] ? ff[i - 1] : 1) % mod;
dfs1(0);
vector<pair<int, int>> gs(mxd[0]);
for (int y = 0, j = ssz(gs) - 1; y != -1; y = tr[y].empty() ? -1 : tr[y][0], j--)
gs[j] = { 1, y };
dfs2(0, gs, { 1, 1, 0, ssz(gs) });
int ans = 0;
for (int i = 0; i < n; i++)
ans = (ans + qpow(1ll * (f[i] - 1 + mod) * g[i] % mod, k)) % mod;
if (l > 0)
{
for (int i = 1; i < n; i++)
ans = (ans - qpow(1ll * (f2[i] - 1 + mod) * (g[i] - 1 + mod) % mod, k) + mod) % mod;
}
cout << ans << endl;
return 0;
}
/*#include <algorithm>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(b!=0){T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}else return y=0,x=1,a;}
template<typename T>T power(T base,T index,T mod)
{
T ans=1%mod;
while(index)
{
if(index&1)ans=ans*base%mod;
base=base*base%mod,index>>=1;
}
return ans;
}
namespace ConstMod
{
template<const ullt p>
class mod_ullt
{
private:
ullt v;
inline ullt chg(ullt w){return(w<p)?w:w-p;}
inline mod_ullt _chg(ullt w){mod_ullt ans;ans.v=(w<p)?w:w-p;return ans;}
public:
mod_ullt():v(0){}
mod_ullt(ullt v):v(v%p){}
bol empty(){return!v;}
inline ullt val(){return v;}
friend bol operator<(mod_ullt a,mod_ullt b){return a.v<b.v;}etVal[2][i])^k;
for(uint i=1;i<n;i++)ans-=(GetVal[1][i]*(GetVal[2][i]-1))^k;
ans.println();
return 0;
}*/
詳細信息
Pretests
Final Tests
Test #1:
score: 4
Accepted
time: 0ms
memory: 30396kb
input:
16 3 1 15 13 7 5 7 3 13 4 13 11 16 9 13 9 11 2 1 6 14 13 11 12 8 9 7 14 10 6 6 16
output:
1243
result:
ok single line: '1243'
Test #2:
score: 4
Accepted
time: 0ms
memory: 30260kb
input:
10 2 2 6 4 7 3 6 5 8 4 9 8 1 7 2 7 6 7 10 4
output:
9430
result:
ok single line: '9430'
Test #3:
score: 4
Accepted
time: 4ms
memory: 30132kb
input:
10 10 9 2 4 1 8 5 8 7 8 10 9 8 2 1 10 8 3 5 6
output:
287143445
result:
ok single line: '287143445'
Test #4:
score: 4
Accepted
time: 4ms
memory: 30236kb
input:
10 2 10 9 5 4 7 10 4 6 8 3 4 4 6 4 2 5 6 1 10
output:
736013382
result:
ok single line: '736013382'
Test #5:
score: 4
Accepted
time: 4ms
memory: 30324kb
input:
497 497 9 421 44 120 434 367 497 332 122 115 101 5 348 14 144 210 359 141 242 439 276 215 289 303 375 28 77 143 428 151 127 457 288 62 351 421 187 25 261 347 257 344 339 452 474 216 387 144 24 167 148 135 133 178 331 274 50 339 369 60 211 350 292 115 76 393 473 475 387 294 332 43 91 368 81 481 27 95...
output:
331917336
result:
ok single line: '331917336'
Test #6:
score: 4
Accepted
time: 3ms
memory: 30668kb
input:
1000 100 1 382 224 432 411 634 456 768 851 345 832 659 985 177 604 834 849 397 593 156 24 43 819 438 78 188 80 936 395 91 529 959 911 104 355 503 618 164 972 505 652 746 845 907 301 662 531 486 660 360 724 340 112 155 499 308 974 123 97 829 600 709 781 415 678 874 272 675 879 583 881 968 414 769 359...
output:
836607737
result:
ok single line: '836607737'
Test #7:
score: 4
Accepted
time: 27ms
memory: 49868kb
input:
49999 29 10 16726 12082 6732 37340 40485 10847 44869 24166 36684 39431 3249 27243 45483 37633 19260 22383 19143 13528 6706 7421 11839 47225 46922 11790 47525 3196 43850 42710 4893 2839 37556 41101 5873 45077 2696 21251 39836 36172 42780 38464 41481 9865 33864 24756 3474 13763 31198 28752 46506 3786 ...
output:
562505285
result:
ok single line: '562505285'
Test #8:
score: 4
Accepted
time: 59ms
memory: 62664kb
input:
99990 95 1 73567 71079 3326 88384 36374 90162 37653 80637 66761 72061 61493 34910 70782 93885 15325 87771 81082 95813 1016 32294 3583 89414 63054 88734 902 70455 89078 71307 5572 73684 90068 2718 7522 87784 1880 77032 9206 13625 40074 66039 84079 94646 7226 26891 10757 47921 52558 82703 77478 24017 ...
output:
625332568
result:
ok single line: '625332568'
Test #9:
score: 4
Accepted
time: 64ms
memory: 61320kb
input:
100000 100 9 71142 34813 51716 56682 16198 52726 21972 98808 8782 18661 64438 93384 62968 16698 66396 20240 57089 24568 53302 66919 46404 72330 31924 16432 72942 87322 42977 1430 31924 75941 59006 24077 93987 11904 11298 45520 31924 66491 52351 81769 98877 37816 48438 29764 10467 60332 46402 82645 3...
output:
854741172
result:
ok single line: '854741172'
Test #10:
score: 4
Accepted
time: 879ms
memory: 432936kb
input:
999992 282751 9 539736 453462 540111 477459 971608 731703 333352 646885 474338 449903 682998 756565 514706 652705 319529 600819 450009 862650 270005 950006 215331 949892 900851 316199 20848 879879 601074 688617 353471 60779 988869 786268 982113 354443 464498 645452 282384 979334 404667 275071 465382...
output:
242487770
result:
ok single line: '242487770'
Test #11:
score: 4
Accepted
time: 24ms
memory: 37180kb
input:
29997 29997 1 17887 27517 28638 28750 17146 20323 2484 14534 14496 9485 28598 1702 16812 20561 12792 10249 21147 12075 26413 21147 23535 12297 12912 2957 16747 4815 3695 4722 15400 11359 12046 1690 23085 4025 15400 29146 11317 21167 21147 27124 26258 22579 27050 28822 21147 12210 23688 24822 16221 1...
output:
208568713
result:
ok single line: '208568713'
Test #12:
score: 4
Accepted
time: 31ms
memory: 44828kb
input:
39999 9999 1 17847 8767 34288 3223 31953 15747 19891 38574 22166 12007 22545 10176 15852 4478 25563 38574 25054 22861 19512 38574 25737 7144 4838 36701 36463 6714 23038 3579 18929 21494 14933 19526 1630 30203 28237 23398 4178 14268 16048 18342 9864 7531 22278 29214 14797 32203 20 13687 3267 27370 29...
output:
622134586
result:
ok single line: '622134586'
Test #13:
score: 4
Accepted
time: 60ms
memory: 44804kb
input:
49937 9618 9 28900 21057 23426 3158 11352 23430 22070 36326 3612 43977 6755 2034 33497 5866 26127 35204 45896 2194 2698 6508 47136 7404 25263 35056 14916 24075 25469 5476 2913 24445 38256 32997 2634 14195 26348 45158 39795 30522 32668 23847 48619 32881 11604 33190 32221 44730 39330 46327 37184 15880...
output:
808296259
result:
ok single line: '808296259'
Test #14:
score: 4
Accepted
time: 52ms
memory: 66260kb
input:
99997 24814 1 70294 6008 96698 51718 85730 12149 7399 68219 19240 98520 6806 60763 60944 9942 95042 84051 52276 11791 92228 26864 31607 4577 50572 55556 91020 39530 99630 58302 46987 75388 13481 8988 73782 79423 13592 71106 68888 24123 69314 52558 1827 1930 2403 39363 71227 97979 62460 62818 93260 8...
output:
889032739
result:
ok single line: '889032739'
Test #15:
score: 4
Accepted
time: 96ms
memory: 75392kb
input:
149934 23430 1 19524 118124 102651 94642 105977 88780 22851 21085 118124 26220 51965 41865 94877 88657 45954 42676 15024 104515 88216 18289 71244 65571 85897 126980 121323 96801 149044 144348 118914 98362 41777 84779 95166 106140 50549 5071 69568 144894 133722 26506 32976 45985 139222 118124 57802 8...
output:
967739919
result:
ok single line: '967739919'
Test #16:
score: 4
Accepted
time: 120ms
memory: 94688kb
input:
199993 199993 10 22574 120810 132171 199046 85192 167635 166147 64640 92778 56014 52056 77741 141487 104029 192429 193787 24289 66737 56456 33117 12406 121250 139510 72340 37754 175679 27730 106773 34512 45901 169159 145205 167199 9455 124988 27796 183030 167303 176967 58418 116279 112701 122931 786...
output:
210281061
result:
ok single line: '210281061'
Test #17:
score: 4
Accepted
time: 127ms
memory: 88048kb
input:
199995 199995 1 74797 7556 81442 135821 185092 167712 42234 63649 134023 46082 134318 22976 128405 107157 36520 80426 167712 198927 132017 118773 288 1341 132649 22081 174449 167712 94580 179706 151008 160583 48868 128462 4161 125098 142488 88139 167712 47267 153225 129410 167712 100469 16050 89116 ...
output:
241088863
result:
ok single line: '241088863'
Test #18:
score: 4
Accepted
time: 120ms
memory: 91092kb
input:
199996 25550 1 153865 144748 17792 151663 128934 59764 43644 133644 130769 176056 95288 123429 93190 140114 194626 118534 30624 86065 30624 103291 63137 117845 45411 57110 93790 4225 44261 92925 163904 119841 194626 20904 26921 194626 191171 32365 50763 194808 133250 162111 174639 5106 39176 139051 ...
output:
346947170
result:
ok single line: '346947170'
Test #19:
score: 4
Accepted
time: 129ms
memory: 100576kb
input:
200000 24970 9 177589 184389 22449 43171 11368 15434 177589 124467 34715 172282 160344 28685 138184 4137 18031 177589 123360 2900 167503 74776 150552 180476 177589 198321 191168 145709 26761 40657 76252 155219 199611 140454 80426 54961 64064 134456 48347 114493 190498 177589 177589 2360 154689 13729...
output:
659235481
result:
ok single line: '659235481'
Test #20:
score: 4
Accepted
time: 134ms
memory: 92360kb
input:
200000 24973 9 118915 67700 120517 143573 66710 142095 140916 9440 144299 173165 179864 150849 108850 86634 183838 27249 56514 33874 45014 108850 185494 52388 160940 76515 27076 33073 194583 114506 127559 66004 44294 183831 7460 108850 198987 150508 45758 70252 59682 157110 49593 150673 67251 108850...
output:
371741367
result:
ok single line: '371741367'
Test #21:
score: 4
Accepted
time: 138ms
memory: 84704kb
input:
199999 15797 9 111155 118437 116181 103286 171596 117870 169742 58066 37077 12461 115452 191571 126892 134514 115497 151658 189077 76880 28368 17080 186378 14214 62745 18534 142023 76880 150833 175023 26865 15461 49984 107836 92202 136608 184737 112189 86026 148269 76880 147485 101065 111876 39958 1...
output:
923057136
result:
ok single line: '923057136'
Test #22:
score: 4
Accepted
time: 980ms
memory: 333404kb
input:
999996 144346 1 424407 435560 510418 674573 150671 452726 128147 920948 510027 239220 972006 448279 281095 505374 655082 730449 15872 689268 70185 87349 741472 521817 723804 255286 811374 494975 443017 139873 406268 753301 20508 211500 191993 316128 730092 917846 868622 770478 738161 787331 87502 24...
output:
243642588
result:
ok single line: '243642588'
Test #23:
score: 4
Accepted
time: 1030ms
memory: 351468kb
input:
999997 139853 10 920585 690093 197610 611492 23489 349039 700388 280314 98990 218300 673469 707504 635638 180992 710821 330460 525503 990906 707504 708854 273138 955457 931868 88040 878331 611354 968123 352800 971264 681683 844600 397899 843885 192964 615112 555275 242987 872652 20593 782797 330349 ...
output:
66295209
result:
ok single line: '66295209'
Test #24:
score: 4
Accepted
time: 1011ms
memory: 333480kb
input:
999955 103989 10 925289 178114 308672 659094 669662 430933 561446 607489 799171 728376 452539 684799 9192 983985 974919 329141 696226 20531 172583 956538 197830 414632 820211 684799 180437 882577 684799 945146 18047 421707 266023 709380 377290 420390 920102 395704 702819 208991 700053 332653 479543 ...
output:
296918790
result:
ok single line: '296918790'
Test #25:
score: 4
Accepted
time: 973ms
memory: 319596kb
input:
999936 123275 9 536599 787920 7994 306084 494368 947491 507729 297675 824018 568122 28934 711706 235386 798753 343255 798753 953136 324491 67553 200106 466356 485763 569760 432140 864787 466356 236533 560892 469895 353561 686792 47275 575895 202643 798753 887888 735885 356054 335977 648100 900249 62...
output:
209607906
result:
ok single line: '209607906'
Extra Test:
score: 0
Extra Test Passed