QOJ.ac
QOJ
ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|
#1517 | #879367 | #9696. Analysis | Nafeeszx | ucup-team987 | Success! | 2025-02-06 00:44:29 | 2025-02-06 00:44:29 |
详细
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 | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#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;
}