用树形dp做的，dp[t][i]表示t及其孩子入度都已经小于等于2并且t这个节点的入度等于i的最优解。

那么转移什么的自己想想就能明白了。

关键在于这个题目会暴栈，所以我用了一次bfs搜索出节点的顺序，然后再计算。

 

#include 
    
     #include 
     
      #include 
      
       using namespace std;const int maxn=1e6+9;struct{    int to,next;}e[maxn*2];int head[maxn],lon;bool text[maxn];void edgeini(){    memset(head,-1,sizeof(head));    lon=-1;}void edgemake(int from,int to){    e[++lon].to=to;    e[lon].next=head[from];    head[from]=lon;}int dp[maxn][3];int from[maxn];void dfs(int t){    int k;    int a1=10,a2=10,ret=0,u;    for(k=head[t];k!=-1;k=e[k].next)    {        u=e[k].to;        if(u==from[t]) continue;        ret++;        dp[t][0]+=dp[u][2]+2;        if(dp[u][1]-dp[u][2]
       
        =1)    dp[t][1]=max(0,dp[t][0]+a1-2);    else    dp[t][1]=dp[t][0];    if(ret>=2)    dp[t][2]=max(0,dp[t][0]+a1+a2-4);    else    dp[t][2]=dp[t][1];//    cout<<0<
        
         =1;i--)    dfs(que[i]);}int main(){    int T;    scanf("%d",&T);    while(T--)    {        memset(dp,0,sizeof(dp));        edgeini();        int n;        scanf("%d",&n);        for(int i=1,from,to;i