首先若存在多个连通块，那么答案显然是$+\infty$。

否则以$m$为根，每棵子树的根节点都最多只能放一个金币，且这些子树之间互不干扰。

对于一棵父亲为$m$的子树，最优方案下一定可以将子树剖分成若干条祖先到孙子的链，每条链中每个点$x$往上贡献$\lfloor\frac{v[x]}{2}\rfloor$个金币，且不能贡献到其它链上去，因此一条有$k$个点的链最多可以放$2^k-1$个金币。

设$f[i][j]$表示考虑$i$的子树，$i$所在链里有$j$个点时最多能放的金币数，枚举链的接法转移即可。

时间复杂度$O(n^2)$。

 

#include
     
      typedef long long ll;const int N=70;const ll inf=1LL<<50;int n,m,i,j,ed,g[N],v[N<<1],nxt[N<<1];char s[N];ll p[N],f[N][N],h[N],ans;inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}inline void up(ll&a,ll b){  if(b>inf)b=inf;  if(a
      
       2000000000)ans=-1;    printf("%lld\n",ans);  }  return 0;}