[Wunder Fund Round 2016 pD][DP] Hamiltonian Spanning Tree

link
You can view official tutorial here.
Here I will explain some points I consider important when trying to solve the problem.
There may be some mistakes in grammar due to my poor English QAQ.
Any correction of algorithm or grammar is welcomed.

It's not hard to find that x>y and x<y are two different problem: One is to use more tree edges as possible while the other is to use less tree edges.

For x>y:

I originally thought that there always exists a way to avoid passing the tree edges since the graph is a complete graph. As a result, I found I was wrong expectedly (?) while trying to prove it. The proof is not hard to figure out. You can view it in the official tutorial.(Hint: Bipartite Graph)

Here's the conclusion for x<y :

if(the graph is a star graph) ans = y*(n-2)+x;
else ans= y*(n-1);

For x<y:

Now the problem turns into finding the minimum path cover of the spanning tree,that is,decompose the spanning tree to less chain as possible.

Now , in my opinion , here comes the most diffcult part of the problem.We can restate the problem as:

Find the maximum number of edges you can choose such that all nodes in the graph are incident to at most 2 edges.

The intuition is 2-matching means a path cover. You can draw some examples if this seems not so intuitive to you.(me,either)

So we can construct a dp solution now:

Let dp[i] the answer of the subtree whose root is i . Since the constraints of the problem is the degree, we can compute dp[i] as we discuss the degree of i.

Now, let dp[i][k] the answer of the subtree whose root is i and i is incident to k edges , 0<=k<=2. For convenience , let dp[i][3] be the answer of i , which is
 max ( dp[i][0] , max( dp[i][1], dp[i][2] ) )

We can compute dp[i][k] this way:

For dp[i][0] , we can see dp[i][0]= (sum of all dp[ i's children][3] ). Since there is no edge among i and its children.So every subtree whose root is i's children is independent.

For dp[i][1] , first we have to choose one of i's child , call it k. the answer will be

dp[i][1]=(sum of all dp[i's children but k][3]) + 1 + max(dp[k][0],dp[k][1])
            =(sum of all dp[i's children][3]) -dp[k][3] +1 + max(dp[k][0],dp[k][1])
the best k would be the k satisfying ( max(dp[k][0],dp[k][1]) - dp[k][3] ) is the biggest among all i's children . It's simple to implement it by maintaining the best choice when checking all children of i.

For dp[i][2] , it's pretty similar to dp[i][1] while choosing two sons instead of one son . Just maintain two best choice of k when checking all children of i . An even more easier way to do it is push every element in vector and sort them while the time complexity will become O(V + ElgE) , which is still acceptable with the constraints of n<=200000.

For dp[i][3] , just get the maximum among dp[i][0],dp[i][1],dp[i][2].

Problem solved in O(V+E).
If you have difficulty implementing the algorithm , here is my code:

#define LL long long
#include<bits/stdc++.h>
using namespace std;
const LL maxn=200000+5;
LL dp[maxn][4];
vector<int> G[maxn];
LL deg[maxn];
void dfs(LL now,LL fa)
{
    for(LL i=0;i<G[now].size();i++) if(G[now][i]!=fa) dfs(G[now][i],now);
    dp[now][0]=dp[now][1]=dp[now][2]=dp[now][3]=0;

    LL best1=0,best2=0;
    for(LL i=0;i<G[now].size();i++)
    {
        int& to=G[now][i];
        if(to==fa) continue;
        dp[now][0]+=dp[to][3];
        if(best1==0) best1=to;
        else if(best2==0)
        {
            if((max(dp[to][0],dp[to][1])-dp[to][3])>(max(dp[best1][0],dp[best1][1])-dp[best1][3]))
                best2=best1,best1=to;
            else best2=to;
        }
        else if((max(dp[to][0],dp[to][1])-dp[to][3])>(max(dp[best1][0],dp[best1][1])-dp[best1][3]))
        {
            swap(best1,best2);
            best1=to;
        }
        else if((max(dp[to][0],dp[to][1])-dp[to][3])>(max(dp[best2][0],dp[best2][1])-dp[best2][3]))
            best2=to;
    }
    if(best1) dp[now][1]=1+dp[now][0]-dp[best1][3]+max(dp[best1][0],dp[best1][1]);
    if(best1 && best2)
    dp[now][2]= 2 + dp[now][0]-dp[best1][3]-dp[best2][3]+max(dp[best1][0],dp[best1][1])+max(dp[best2][0],dp[best2][1]);
    dp[now][3]=max(dp[now][0],max(dp[now][1],dp[now][2]));
}
int main()
{
    LL n,x,y;
    scanf("%I64d%I64d%I64d",&n,&x,&y);
    for(LL i=0,a,b;i<n-1;i++)
    {
        scanf("%I64d%I64d",&a,&b);
        G[a].push_back(b);
        G[b].push_back(a);
        deg[a]++,deg[b]++;
    }
    if(x>y) 
    {
        for(LL i=1;i<=n;i++) if(deg[i]==n-1) {printf("%I64d\n",y*(n-2)+x);return 0;}
        printf("%I64d\n",y*(n-1));
    }
    else
    {
        dfs(1,-1);
        printf("%I64d\n",dp[1][3]*x+(n-1-dp[1][3])*y);
    }
}