哪些是网站建设,北京网站设计公司哪儿济南兴田德润简介,js网站登录怎么做,建筑公司网站设计详情CF1779F Xorcerer’s Stones 树形dp记录路径 首先我们分析一下操作。 对于奇树#xff0c;进行一次操作后#xff0c;其异或和不变#xff1b;对于偶树#xff0c;进行一次操作后#xff0c;其异或和为0。 如果我们能让所有点异或和为0#xff0c;只要在根节点再进行一次…CF1779F Xorcerer’s Stones 树形dp记录路径 首先我们分析一下操作。 对于奇树进行一次操作后其异或和不变对于偶树进行一次操作后其异或和为0。 如果我们能让所有点异或和为0只要在根节点再进行一次操作就可以得到一种合法操作方案考虑树形dp出是否存在一种方案, d p u , j dp_{u,j} dpu,j表示以 u u u为根节点的子树内是否存在异或和为 j j j的操作方案。合并很简单但是对于 s z u sz_u szu为偶数时不论其子树内操作如何都可以进行一次操作使得 d p u , 0 1 dp_{u,0}1 dpu,01。 对于方案的记录我们开一个 p r e v , j x o r k j pre_{v,jxork}j prev,jxorkj表示 d p u , j x o r k 1 dp_{u,jxork}1 dpu,jxork1这种方案是在儿子异或和为 k k k的情况下根节点异或和为 j j j的情况下合并转移而来的因为dp时 u u u的儿子由前往后遍历转移那么输出路径时就应该由后往前遍历
#include bits/stdc.h
#define ll long long
struct node{int x,y;
};
void solve(){int n;std::cinn;std::vectorint a(n1);for (int i1;in;i){std::cina[i];}std::vectorstd::vectorint e(n1);for (int i2;in;i){int x;std::cinx;e[x].push_back(i);e[i].push_back(x);}std::vectorint sz(n1);std::vectorstd::vectorint dp(n1,std::vectorint(32)),pre(n1,std::vectorint(32));std::functionvoid(int,int) dfs[](int u,int fa){sz[u]1;dp[u][a[u]]1;for (auto v:e[u]){if (vfa) continue;dfs(v,u);std::vectorint use(32);std::swap(dp[u],use);for (int j0;j32;j){if (!use[j]) continue;for (int k0;k32;k){if (!dp[v][k]) continue;dp[u][j^k]1;pre[v][j^k]j;}}sz[u]sz[v];}if (!(sz[u]1)){dp[u][0]1;}};dfs(1,-1);std::vectorint ans;std::functionvoid(int,int,int) prin[](int u,int fa,int sum){if (!(sz[u]1)!sum){ans.push_back(u);}reverse(e[u].begin(),e[u].end());for (auto v:e[u]){if (vfa) continue;prin(v,u,sum^pre[v][sum]);sumpre[v][sum];}};if (dp[1][0]){prin(1,-1,0);std::coutans.size()1\n;for (auto i:ans){std::couti ;}std::cout1;}else{std::cout-1;}
}
int main(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);solve();return 0;
}
