QOJ.ac
QOJ
ID | Submission ID | Problem | Hacker | Owner | Result | Submit time | Judge time |
---|---|---|---|---|---|---|---|
#1517 | #879367 | #9696. Analysis | Nafeeszx | ucup-team987 | Success! | 2025-02-06 00:44:29 | 2025-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'
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#879367 | #9696. Analysis | ucup-team987# | WA | 382ms | 188796kb | C++20 | 958b | 2025-02-02 00:05:52 | 2025-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;
}