QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#709449 | #8758. Menji 和 gcd | szy10010# | RE | 0ms | 0kb | C++20 | 1.6kb | 2024-11-04 14:47:53 | 2024-11-04 14:47:53 |
Judging History
answer
#include<iostream>
#include<map>
#include<cmath>
#include<string>
#include<vector>
#include<cstring>
#include<algorithm>
#include<unordered_map>
#include<queue>
#define pb emplace_back
#define fi first
#define se second
#define int long long
#define all(x) (x).begin(),(x).end()
#define _for(i, a) for(int i = 0; i < (a); ++i)
#define _rep(i, a, b) for(int i = (a);i <= (b); ++i)
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define u1 (u<<1)
#define u2 (u<<1|1)
//#define endl '\n'
using namespace std;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const int P=1e9+7;
const int N=2e5+20,M=2*N;
int n;
//res维护以i为根的答案
int res[N],sum[N],sz[N],w[N];
vector<int> v[N];
//bool st[N];
bool cmp(int a,int b)
{
int ta=res[a]+(sz[a])*sum[b]+res[b];
int tb=res[b]+(sz[b])*sum[a]+res[a];
// cout<<a<<" "<<b<<" "<<res[a]<<" "<<res[b]<<" "<<sz[a]<<" "<<sz[b]<<" "<<sum[a]<<" "<<sum[b]<<" "<<ta<<" "<<tb<<endl;
return ta>tb;
}
int dfs(int u){
// st[u]=true;
// cout<<" "<<u<<endl;
sz[u]=1;
sum[u]=w[u];
res[u]=w[u];
for(auto j:v[u])
{
dfs(j);
sz[u]+=sz[j];
sum[u]+=sum[j];
}
if(v[u].size())
{
sort(all(v[u]),cmp);
int nowres=0,nowsz=1;
for(auto i:v[u])
{
nowres+=nowsz*sum[i]+res[i];
nowsz+=sz[i];
}
res[u]+=nowres;
}
return res[u];
}
void solve(){
cin>>n;
_rep(i,1,n) cin>>w[i];
_rep(i,2,n){
int fa;
cin>>fa;
v[fa].pb(i);
}
cout<<dfs(1);
return;
}
signed main(){
IOS;
int T=1;
// cin>>T;
_rep(i,1,T){
solve();
}
return 0;
}
详细
Test #1:
score: 0
Runtime Error
input:
10 1 2 2 4 6 10 11 21 147 154 1470 1540 2890 3028 998244353 1000000007 34827364537 41029384775 147147147147 154154154154