网上写作最好的网站,贝壳房源网,眉山网站建设,网站关键词是什么意思组合树
题目大意#xff1a;
有一棵树#xff0c;每个点都有自己的原颜色和目标颜色#xff08;黑或白#xff09;#xff0c;现在深度不小于k的点可以让自己祖宗k代k个点的颜色全部取反#xff0c;现在问当前树是否能变成目标树
输入样例
2 3 2 1 2 2 3 0 0 0 1 0 1…组合树
题目大意
有一棵树每个点都有自己的原颜色和目标颜色黑或白现在深度不小于k的点可以让自己祖宗k代k个点的颜色全部取反现在问当前树是否能变成目标树
输入样例
2 3 2 1 2 2 3 0 0 0 1 0 1 3 2 1 2 2 3 0 0 0 1 1 1
输出样例
Yes No
样例解释
在第一个例子中第一次选择2号点操作1,2号点被翻转第二次选择3 号点操作2,3号点被翻转。即达成目标状态。 可以证明无法将初始状态经过操作变为目标状态。
数据范围
对于前 10% 的数据n≤5 对于前 30% 的数据n≤20 对于前 50% 的数据n≤2000 对于前 70% 的数据n≤50000 对于全部数据T≤10, k≤n≤2×105保证数据给出的是一棵树。
解题思路
用dfs确定点之间的关系顺便算出第k代祖先然后根据拓扑序判断是否需要改变如果要就用差分记录在第k代祖先的地方打上一个符号然后在下一个点也打上一个相反的符号然后判断是否能行即可
代码
#includequeue
#includecstdio
#includecstring
#includeiostream
using namespace std;
int n,t,k,x,y,h,tot,f[1000500],fv[1000500],sv[1000500],dt[1000500],nos[1000500],dad[1000500],dadk[1000500],head[1000500];
struct rec
{int to,next;
}a[1000500];
void dfs(int now,int dep)
{if (depk) dadk[now]dt[dep-k1];//第k代祖先dt表示当前在某一行的是哪个数for (int ihead[now];i;ia[i].next)//遍历if (!dad[a[i].to])//消掉bug{dad[a[i].to]now;//记录dt[dep1]a[i].to;nos[now];//儿子数dfs(a[i].to,dep1);}
}
void js()
{tot0;memset(f,0,sizeof(f));memset(nos,0,sizeof(nos));memset(dad,0,sizeof(dad));memset(dadk,0,sizeof(dadk));memset(head,0,sizeof(head));scanf(%d %d,n,k);for (int i1;in;i){scanf(%d %d,x,y);a[tot].toy;a[tot].nexthead[x];head[x]tot;a[tot].tox;a[tot].nexthead[y];head[y]tot;}for (int i1;in;i) scanf(%d,fv[i]);for (int i1;in;i) scanf(%d,sv[i]);dt[1]1;dad[1]-1;dfs(1,1);queueintd;for (int i1;in;i)if (!nos[i])d.push(i);while(!d.empty())//拓扑排序{hd.front();d.pop();if ((fv[h]f[h])%2!sv[h])//不符合的if (!dadk[h])//不能加{printf(No\n);//就不行了return;}else f[dad[h]],f[dad[dadk[h]]]--;//可以就打上差分符号f[dad[h]]f[h];//继承上去nos[dad[h]]--;if (!nos[dad[h]]) d.push(dad[h]);}printf(Yes\n);
}
int main()
{scanf(%d,t);while (t--) js();
}
