QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#1517#879367#9696. AnalysisNafeeszxucup-team987Success!2025-02-06 00:44:292025-02-06 00:44:29

Details

Extra Test:

Wrong Answer
time: 1ms
memory: 3584kb

input:

1 5 7

output:

500000000000000000

result:

wrong answer 1st numbers differ - expected: '0', found: '500000000000000000'

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#879367#9696. Analysisucup-team987#WA 382ms188796kbC++20958b2025-02-02 00:05:522025-02-06 00:55:02

answer

#include<iostream>
#include<vector>
#include<cassert>
using namespace std;
int N,A,B;
vector<int>G[5<<17];
long long dp[5<<17][3][4];
void dfs(int u,int p)
{
	for(int i=0;i<3;i++)for(int j=0;j<4;j++)dp[u][i][j]=1e18;
	if(G[u].size()%2==0)dp[u][0][0]=0;
	else
	{
		dp[u][0][1<<0]=0;
		dp[u][0][1<<1]=B;
		dp[u][1][0]=0;
	}
	for(int v:G[u])if(v!=p)
	{
		dfs(v,u);
		long long nx[3][4];
		for(int i=0;i<3;i++)for(int j=0;j<4;j++)nx[i][j]=1e18;
		for(int i=0;i<3;i++)for(int j=0;j<4;j++)
		{
			for(int k=0;i+k<=2;k++)for(int l=0;l<4;l++)
			{
				nx[i+k][j^l]=min(nx[i+k][j^l],dp[u][i][j]+dp[v][k][l]+(l&1?A+A:0));
			}
		}
		for(int i=0;i<3;i++)for(int j=0;j<4;j++)dp[u][i][j]=nx[i][j];
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>N>>A>>B;
	for(int i=1;i<N;i++)
	{
		int u,v;cin>>u>>v;
		u--,v--;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(0,-1);
	cout<<dp[0][2][0]/2<<endl;
}