QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#698172 | #9530. A Game On Tree | Rykony | WA | 2ms | 3652kb | C++20 | 1.2kb | 2024-11-01 17:57:29 | 2024-11-01 17:57:29 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using LL=long long;
const LL mod=998244353;
LL qpow(LL a,LL n)
{
LL ans=1;
while (n){
if (n&1) ans=ans*a%mod;
a=a*a%mod;
n>>=1;
}
return ans;
}
int main()
{
cin.tie(0)->sync_with_stdio(false);
int _=1;
cin>>_;
while (_--){
int n;
cin>>n;
vector <int> v[n+10];
for (int i=1;i<n;i++){
int x,y;
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
vector <LL> siz(n+10,0),sum(n+10,0);
LL ans=0;
function<void(int,int)> dfs=[&](int d,int fa)
{
// cout<<d<<" ";
siz[d]=1;
LL fin=0,pin=0;
for (auto p:v[d]){
if (p==fa) continue;
dfs(p,d);
siz[d]+=siz[p];
sum[d]=(sum[d]+siz[p]*siz[p])%mod;
ans=(ans+siz[p]*siz[p]%mod*(n-siz[p])*(n-siz[p])%mod)%mod;
fin=(fin+sum[p])%mod;
pin=(pin+sum[p]*sum[p])%mod;
ans=(ans+2*((n-siz[p])*(n-siz[p])%mod*(sum[p]-(siz[p]*siz[p])%mod+mod)%mod)%mod)%mod;
}
sum[d]=(sum[d]+siz[d]*siz[d])%mod;
ans=((ans+fin*fin%mod)%mod-pin+mod)%mod;
};
dfs(1,0);
// for (int i=1;i<=n;i++) cout<<siz[i]<<" "<<sum[i]<<'\n';
LL fm=n%mod*n%mod*(n-1)%mod*(n-1)%mod*qpow(4,mod-2)%mod;
ans=ans*qpow(fm,mod-2)%mod;
cout<<ans<<'\n';
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3580kb
input:
2 3 1 2 2 3 5 1 2 1 5 3 2 4 2
output:
443664158 918384806
result:
ok 2 lines
Test #2:
score: -100
Wrong Answer
time: 2ms
memory: 3652kb
input:
1000 7 3 6 4 3 5 3 2 6 1 4 7 1 12 5 7 10 7 2 10 11 2 1 7 8 1 4 2 9 11 6 9 12 11 3 5 6 2 5 1 2 4 5 6 4 3 6 5 2 5 1 5 4 5 3 2 8 1 8 2 8 4 2 6 1 5 6 7 6 3 8 8 3 8 7 3 4 8 6 4 2 7 5 2 1 4 4 3 1 4 3 2 1 6 5 1 6 1 2 5 3 5 4 2 12 8 11 5 11 12 8 3 12 6 12 2 3 4 6 10 11 1 5 9 5 7 5 9 6 1 7 6 4 7 8 7 5 4 9 6 ...
output:
934863761 939119690 381551177 259543533 495302366 760142705 776412276 292818345 628600613 203346074 791817282 243399088 247498602 616913179 298240908 198662952 507601297 584006902 38943856 154050056 359102138 109501295 816465290 98592036 758665710 166649059 961765302 589524409 310564911 431340154 81...
result:
wrong answer 1st lines differ - expected: '948445317', found: '934863761'