读错题了有没有呀，原来 lamps 是在边上的呀，当成是在点上的了，无语。
直接一个dfs 就可以 从叶子节点开始，如果有必要转换 lamp 的状态则加一个仅包含 这个 lamp 的段
然后向上扩展，对于某个子树，根据扩展上来的段的个数，将偶数段进行合并（这是最优选择），然后可能剩
一个或者0个段没用上，再根据这个节点到父节点的lamp的状态进行分析是否要将剩下的段向上扩展。
直到根节点。
由于所给边的特殊性，可以直接遍历。
代码：
#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<set>
#include<map> #define ll long long
#define ull unsigned long long
using namespace std;
const int INF=0x3f3f3f3f;
/*
class TurnOnLamps
{
public:
int minimize(vector <int> r, string S, string I)
{
int x[100]={0};
int n=r.size();
int sum=0;
for(int i=n-1;i>=0;--i)
{
if(I[i]=='1')
{
if((S[i]=='0'&&x[i+1]==0)||(S[i]=='1'&&x[i+1]==1))
{
++sum;
x[i+1]^=1;
}
}
x[r[i]]^=x[i+1];
}
return (sum+1)/2;
}
};
*/
const int N=100;
int head[N],cnt;
struct node
{
int j,next;
int state,im;
}edge[N];
int dp[N];
int x[N];
void add(int i,int j,int state,int im)
{
edge[cnt].j=j;
edge[cnt].state=state;
edge[cnt].im=im;
head[i]=cnt++;
}
int dfs(int x,int S,int I)
{
int sum=0;
for(int t=head[x];t!=-1;t=edge[t].next)
{
sum+=dfs(edge[t].j,edge[t].state,edge[t].im);
}
dp[x]=sum/2;
int tmp=sum%2;
if(I==0)
return tmp;
else
{
if(S==1&&tmp==1)
{dp[x]+=1;return 0;}
if(S==1&&tmp==0)
return 0;
if(S==0&&tmp==0)
return 1;
if(S==0&&tmp==1)
return 1;
}
return 0;
}
class TurnOnLamps
{
public:
int minimize(vector <int> r, string S, string I)
{
memset(head,-1,sizeof(head));cnt=0;
for(unsigned int i=0;i<r.size();++i)
{
add(r[i],i+1,S[i]-48,I[i]-48);
}
int tmp=dfs(0,0,0);
for(unsigned int i=0;i<r.size()+1;++i)
tmp+=dp[i];
return tmp;
}
};