QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#380198#8570. Idola-Treeucup-team1447#WA 3325ms90436kbC++144.6kb2024-04-06 21:41:302024-04-06 21:41:31

Judging History

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

  • [2024-04-06 21:41:31]
  • 评测
  • 测评结果:WA
  • 用时:3325ms
  • 内存:90436kb
  • [2024-04-06 21:41:30]
  • 提交

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'