組合樹

題目大意：

有一棵樹，每個點都有自己的原顏色和目標顏色（黑或白），現在深度不小于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代祖先的地方打上一個符號，然后在下一個點也打上一個相反的符號，然后判斷是否能行即可

代碼：

#include<queue> #include<cstdio> #include<cstring> #include<iostream> 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 (dep>=k) dadk[now]=dt[dep-k+1];//第k代祖先，dt表示當前在某一行的是哪個數for (int i=head[now];i;i=a[i].next)//遍歷if (!dad[a[i].to])//消掉bug{dad[a[i].to]=now;//記錄dt[dep+1]=a[i].to;nos[now]++;//兒子數dfs(a[i].to,dep+1);} } void js() {tot=0;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 i=1;i<n;++i){scanf("%d %d",&x,&y);a[++tot].to=y;a[tot].next=head[x];head[x]=tot;a[++tot].to=x;a[tot].next=head[y];head[y]=tot;}for (int i=1;i<=n;++i) scanf("%d",&fv[i]);for (int i=1;i<=n;++i) scanf("%d",&sv[i]);dt[1]=1;dad[1]=-1;dfs(1,1);queue<int>d;for (int i=1;i<=n;++i)if (!nos[i])d.push(i);while(!d.empty())//拓撲排序{h=d.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(); }

總結

以上是生活随笔為你收集整理的【dfs】【拓扑排序】组合树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。