結果

問題 No.3343 Distance Sum of Large Tree
コンテスト
ユーザー kotatsugame
提出日時 2025-11-13 23:19:17
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,484 bytes
コンパイル時間 946 ms
コンパイル使用メモリ 84,952 KB
実行使用メモリ 10,152 KB
最終ジャッジ日時 2025-11-13 23:19:29
合計ジャッジ時間 4,122 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 2 WA * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<algorithm>
#include<vector>
#include<cassert>
#include<atcoder/modint>
using namespace std;
using mint=atcoder::modint998244353;
int N;
mint Asum;
int A[1<<17],B[1<<17],C[1<<17],P[1<<17];
vector<int>G[1<<17];
mint ans;
mint dfs(int u,int p)
{
	{//u to u
		//sum[k=1..A[u]-1] k*(A[u]-k)
		ans+=mint(A[u])*A[u]*(A[u]-1)/2;
		ans-=mint(A[u])*(A[u]-1)*(2*A[u]-1)/6;
	}
	mint ch=A[u];
	vector<mint>V;
	for(int v:G[u])
	{
		mint t=dfs(v,u);
		V.push_back(t);
		ch+=t;
		{//u to v
			mint p=P[v];
			mint c=p*(p+1)/2+(A[u]-p-1)*(A[u]-p)/2;
			ans+=c*t;
		}
		{//u or pr to v or ch
			ans+=(Asum-t)*t;
		}
	}
	vector<pair<int,mint> >VP;
	for(int i=0;i<V.size();i++)
	{
		mint t=V[i];
		int v=G[u][i];
		ans+=(Asum-ch)*t*abs(B[u]-P[v]);
		VP.push_back(make_pair(P[v],t));
	}
	sort(VP.begin(),VP.end(),[](pair<int,mint>l,pair<int,mint>r){return l.first<r.first;});
	mint R=ch-A[u],L=0;
	for(int i=0;i<VP.size();i++)
	{
		R-=VP[i].second;
		ans-=R*VP[i].first*VP[i].second;
		ans+=L*VP[i].first*VP[i].second;
		L+=VP[i].second;
	}
	{//u to pr
		mint t=Asum-ch;
		mint p=B[u];
		mint c=p*(p+1)/2+(A[u]-p-1)*(A[u]-p)/2;
		ans+=c*t;
	}
	return ch;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>N;
	for(int i=0;i<N;i++)cin>>A[i],Asum+=A[i];
	for(int i=1;i<N;i++)cin>>B[i],B[i]--;
	for(int i=1;i<N;i++)cin>>C[i],C[i]--;
	for(int i=1;i<N;i++)cin>>P[i],P[i]--;
	for(int i=1;i<N;i++)G[P[i]].push_back(i);
	dfs(0,-1);
	ans*=2;
	cout<<ans.val()<<endl;
}
0