首先很容易可以得到另f(i,j)表示第i盏灯的父亲是否点亮所以j=0|1如果父亲放了，那么自己放或者不放都可以那么f(i,j)=max{

∑f(ison,0)∑f(ison,1)}，如果父亲没有放置，那么自己必须放那么f(i,0)=∑f(ison,1)但是这个时候要让被灯照亮两次的边尽量多，那么应该让被照亮一次的边尽量的少，那么另m=n×x+yx代表覆盖当前的子树的灯的数量，y代表当前子树中覆盖完成的最少的被照亮一次的边的数量前提是让y的最大值小于n那么这样x就成为了首要重要的权值，y是次要的然后dp方程改一下

f(i,0)=(∑f(ison,1))+1

加1是因为自己和自己的父亲又有一条边被照亮一次所以加1，

f(i,1)=max{

(∑f(ison,0))+1,∑f(ison,1)}

#include 
     
      #include 
      
       #include 
       
        using namespace std;const int MAXN = 1000;struct node{    int v;    node *next;}Edges[MAXN*2+10], *ecnt=Edges, *adj[MAXN+10];void addedge(int u, int v){    ++ecnt;    ecnt->v = v;    ecnt->next = adj[u];    adj[u] = ecnt;}int f[MAXN+10][2];int dp(int u,int md,int fa){    if(f[u][md] != -1) return f[u][md];    int &ans = f[u][md]; ans = 2000;    for(node *p=adj[u];p;p=p->next) if(p->v != fa){        ans += dp(p->v, 1, u);    }    if(md==0&&fa>=0) ans++;    if(md||fa<0){        int tmp = 0;        for(node *p=adj[u];p;p=p->next) if(p->v != fa){            tmp += dp(p->v, 0, u);        }        if(fa>=0) tmp++;        ans = min(ans, tmp);    }    return ans;}int sons[MAXN+10];void Getsons(int u, int fa){    sons[u] = 1;    for(node *p=adj[u];p;p=p->next) if(p->v!=fa){        Getsons(p->v, u);        sons[u] += sons[p->v];    }}int main(){    int T, n, m, u, v, a1, a2, a3;    scanf("%d", &T);    while(T--){        a1 = a2 = a3 = 0;        memset(f, -1, sizeof f);        memset(adj, 0, sizeof adj);        ecnt = Edges;        scanf("%d%d", &n, &m);        for(int i=1;i<=m;i++){            scanf("%d%d", &u, &v);            addedge(u, v); addedge(v, u);        }        for(int i=0;i