QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#380198 | #8570. Idola-Tree | ucup-team1447# | WA | 3325ms | 90436kb | C++14 | 4.6kb | 2024-04-06 21:41:30 | 2024-04-06 21:41:31 |
Judging History
answer
// what is matter? never mind.
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2")
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define ull unsigned long long
#define int long long
#define i128 __int128
using namespace std;
inline int read()
{
char c=getchar();int x=0;bool f=0;
for(;!isdigit(c);c=getchar())f^=!(c^45);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
if(f)x=-x;return x;
}
#define mod 998244353
struct modint{
int x;
modint(int o=0){x=o;}
modint &operator = (int o){return x=o,*this;}
modint &operator +=(modint o){return x=x+o.x>=mod?x+o.x-mod:x+o.x,*this;}
modint &operator -=(modint o){return x=x-o.x<0?x-o.x+mod:x-o.x,*this;}
modint &operator *=(modint o){return x=1ll*x*o.x%mod,*this;}
modint &operator ^=(int b){
modint a=*this,c=1;
for(;b;b>>=1,a*=a)if(b&1)c*=a;
return x=c.x,*this;
}
modint &operator /=(modint o){return *this *=o^=mod-2;}
friend modint operator +(modint a,modint b){return a+=b;}
friend modint operator -(modint a,modint b){return a-=b;}
friend modint operator *(modint a,modint b){return a*=b;}
friend modint operator /(modint a,modint b){return a/=b;}
friend modint operator ^(modint a,int b){return a^=b;}
friend bool operator ==(modint a,modint b){return a.x==b.x;}
friend bool operator !=(modint a,modint b){return a.x!=b.x;}
bool operator ! () {return !x;}
modint operator - () {return x?mod-x:0;}
bool operator <(const modint&b)const{return x<b.x;}
};
inline modint qpow(modint x,int y){return x^y;}
vector<modint> fac,ifac,iv;
inline void initC(int n)
{
if(iv.empty())fac=ifac=iv=vector<modint>(2,1);
int m=iv.size(); ++n;
if(m>=n)return;
iv.resize(n),fac.resize(n),ifac.resize(n);
For(i,m,n-1){
iv[i]=iv[mod%i]*(mod-mod/i);
fac[i]=fac[i-1]*i,ifac[i]=ifac[i-1]*iv[i];
}
}
inline modint C(int n,int m){
if(m<0||n<m)return 0;
return initC(n),fac[n]*ifac[m]*ifac[n-m];
}
inline modint sign(int n){return (n&1)?(mod-1):(1);}
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;
#define maxn 500005
#define inf 0x3f3f3f3f
int n,c;
vi e[maxn];
int rt;
modint out=0;
__int128 ans;
int t[maxn],m,pos[maxn];
__int128 val[maxn];
int fa[maxn];
int s[maxn],sz[maxn],ssz[maxn];
void dfs1(int u,int pa){
fa[u]=pa;
sz[u]=1;
ssz[u]=0;
for(int v:e[u])
if(v!=pa){
dfs1(v,u),sz[u]+=sz[v];
ans+=ssz[u]*ssz[v]*2;
ssz[u]+=ssz[v];
}
ssz[u]+=sz[u];
if(pa && e[u].size()==1){
t[++m]=u;
}
}
void dfs2(int u,int pa){
for(int v:e[u])if(v!=pa){
s[v]=s[u];
s[v]-=sz[v],s[v]+=n-sz[v];
dfs2(v,u);
}
}
int seq[10000007];
pii tr[maxn<<2];
int leaf[maxn];
void up(int p){
tr[p]=min(tr[p<<1],tr[p<<1|1]);
}
void build(int p,int l,int r){
if(l==r)return leaf[l]=p,tr[p]=mkp(val[l],l),void();
int mid=l+r>>1;
build(p<<1,l,mid),build(p<<1|1,mid+1,r),up(p);
}
void upd(int u){
int p=leaf[u];
tr[p]=mkp(val[u],u);
while(p>>=1) up(p);
}
modint S3(modint x){
return x*x*x;
}
int nxt[maxn],pre[maxn];
void work()
{
n=read(),c=read();
For(i,1,n)e[i].clear(),sz[i]=s[i]=fa[i]=0;
ans=0,out=0,m=0;
For(i,2,n){
int u=read(),v=read();
e[u].pb(v),e[v].pb(u);
}
rt=1;
For(i,1,n)if(e[i].size()>1){
rt=i;
break;
}
dfs1(rt,0);
For(i,1,n) if(i!=rt) s[rt]+=sz[i];
dfs2(rt,0);
For(i,1,m) {
// cout<<"t,st "<<t[i]<<" "<<s[t[i]]-(n-1)<<"\n";
pos[i]=1;
int u=i;
val[u]=(s[t[u]]-(n-1))*2+(n-1)*(pos[u]*2+1)-(pos[u]-1)*2;
}
priority_queue< pii,vector<pii>,greater<pii> > q;
For(i,1,m) q.push(mkp(val[i],i));
// int s2=0;
// For(i,1,n) s2+=sz[i];
For(i,1,n) if(i!=rt) ans+=(n-sz[i])*sz[i],ans+=(n-sz[i])*(ssz[i]-sz[i])*2;
// cout<<ans<<"\n";
// ans=15;
// cout<<ans<<"\n";
out+=S3(ans%mod);
int x=q.top().se; q.pop();
pre[x]=nxt[x]=x;
int u=x;
For(i,1,c-(n-1)){
u=nxt[u];
ans+=val[u];
ans+=(i-1)*2;
++pos[u];
// val[u]+=(n-1)*2;
val[u]=(s[t[u]]-(n-1))*2+(n-1)*(pos[u]*2+1)-(pos[u]-1)*2;
// val[u]=(s[t[u]]-(n-1))*2+(n-1)+2+(n-2)*(pos[u]*2);
while(q.size() && q.top().fi<=val[u]){
int u1=pre[u];
int x=q.top().se; q.pop();
nxt[u1]=x,pre[u]=x;
nxt[x]=u,pre[x]=u1;
}
// cout<<ans<<"\n";
out+=S3(ans%mod);
}
cout<<out.x<<"\n";
}
signed main()
{
// freopen("data.in","r",stdin);
// freopen("my.out","w",stdout);
int T=read();
while(T--)work();
return 0;
}
/*
1
5 10
1 4
1 3
1 2
5 4
1 2 3
*/
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 33108kb
input:
2 4 3 1 4 1 3 2 1 4 4 1 4 1 3 2 1
output:
3375 25327
result:
ok 2 tokens
Test #2:
score: 0
Accepted
time: 3ms
memory: 33736kb
input:
4 4 3 1 4 1 3 2 1 4 4 1 4 1 3 2 1 5 4 1 4 1 3 1 2 5 4 5 5 1 4 1 3 1 2 5 4
output:
3375 25327 54872 249984
result:
ok 4 tokens
Test #3:
score: 0
Accepted
time: 2950ms
memory: 90228kb
input:
4 300000 50000000 216838 200677 44849 12926 125086 157230 26195 29767 241694 21336 21336 24457 105861 84565 184655 45583 175336 97945 286044 30927 295273 249694 109469 1566 193560 251229 176229 288707 206166 13532 166218 264413 299977 95587 159105 48116 57912 82606 97296 193689 115029 121192 68068 1...
output:
968050473 546482457 9595680 694101802
result:
ok 4 tokens
Test #4:
score: 0
Accepted
time: 3325ms
memory: 88456kb
input:
4 300000 49999999 260729 131757 51432 46938 257303 178692 218606 108144 299084 259822 82091 231405 101255 218808 287507 101249 29597 151244 43164 198032 122336 162072 177969 62812 277824 35758 182087 258797 235155 33806 188695 76915 289006 141702 39100 183183 224949 156588 9827 173233 27349 286822 1...
output:
283884918 837489229 12901428 323340145
result:
ok 4 tokens
Test #5:
score: -100
Wrong Answer
time: 3233ms
memory: 90436kb
input:
4 300000 50000000 187086 121551 163664 292500 40569 125891 280767 56246 127162 299705 207527 280767 252551 217178 73197 278560 274282 31937 121290 280767 220367 278560 187814 40569 187372 278560 95157 131908 119390 161684 202404 283778 226289 130192 294021 278560 50286 102006 21592 222623 285215 237...
output:
899771809 364539310 683543335 559022036
result:
wrong answer 1st words differ - expected: '4850582', found: '899771809'