响应式网站自助建站,知名网站制作服务,做网站算经商吗,天元建设集团有限公司审计项目登录—专业IT笔试面试备考平台_牛客网
题意#xff1a; 思路#xff1a;
这种是典中典中典#xff0c;对于gcd#xff0c;背包问题都是一样的处理方式
预处理出前缀lca和后缀lca#xff0c;枚举哪个消失即可#xff0c;可以统计方案数
Code#xff1a;
#include 思路
这种是典中典中典对于gcd背包问题都是一样的处理方式
预处理出前缀lca和后缀lca枚举哪个消失即可可以统计方案数
Code
#include bits/stdc.hconstexpr int N 2e5 10;
constexpr int mod 1e9 7;
constexpr int Inf 0x3f3f3f3f;
constexpr double eps 1e-10;std::vectorint adja[N], adjb[N];int n, k;
int x[N];
int a[N], b[N];
int pa[N], pb[N];
int depa[N], depb[N];
int Fa[N][33], Fb[N][33];
int prea[N], sufa[N], preb[N], sufb[N];void dfs1(int u, int fa) {depa[u] depa[fa] 1;Fa[u][0] fa;for (int j 1; j 30; j ) Fa[u][j] Fa[Fa[u][j - 1]][j - 1];for (auto v : adja[u]) {if (v fa) continue;dfs1(v, u);}
}
void dfs2(int u, int fa) {depb[u] depb[fa] 1;Fb[u][0] fa;for (int j 1; j 30; j ) Fb[u][j] Fb[Fb[u][j - 1]][j - 1];for (auto v : adjb[u]) {if (v fa) continue;dfs2(v, u);}
}
int lca_a(int u, int v) {if (depa[u] depa[v]) std::swap(u, v);for (int j 30; j 0; j --) {if (depa[Fa[u][j]] depa[v]) {u Fa[u][j];}}if (u v) return u;for (int j 30; j 0; j --) {if (Fa[u][j] ! Fa[v][j]) {u Fa[u][j];v Fa[v][j];}}return Fa[u][0];
}
int lca_b(int u, int v) {if (depb[u] depb[v]) std::swap(u, v);for (int j 30; j 0; j --) {if (depb[Fb[u][j]] depb[v]) {u Fb[u][j];}}if (u v) return u;for (int j 30; j 0; j --) {if (Fb[u][j] ! Fb[v][j]) {u Fb[u][j];v Fb[v][j];}}return Fb[u][0];
}
void solve() {std::cin n k;for (int i 1; i k; i ) std::cin x[i];for (int i 1; i n; i ) {std::cin a[i];}for (int i 2; i n; i ) {std::cin pa[i];adja[pa[i]].push_back(i);adja[i].push_back(pa[i]);}for (int i 1; i n; i ) {std::cin b[i];}for (int i 2; i n; i ) {std::cin pb[i];adjb[pb[i]].push_back(i);adjb[i].push_back(pb[i]);}dfs1(1, 0);dfs2(1, 0);prea[1] x[1];for (int i 2; i k; i ) {prea[i] lca_a(prea[i - 1], x[i]);}preb[1] x[1];for (int i 2; i k; i ) {preb[i] lca_b(preb[i - 1], x[i]);}sufa[k] x[k];for (int i k - 1; i 1; i --) {sufa[i] lca_a(sufa[i 1], x[i]);}sufb[k] x[k];for (int i k - 1; i 1; i --) {sufb[i] lca_b(sufb[i 1], x[i]);}int ans 0;int cur1 sufa[2];int cur2 sufb[2];if (a[cur1] b[cur2]) ans ;for (int i 2; i k - 1; i ) {int cur1 lca_a(prea[i - 1], sufa[i 1]);int cur2 lca_b(preb[i - 1], sufb[i 1]);if (a[cur1] b[cur2]) ans ;};cur1 prea[k - 1];cur2 preb[k - 1];if (a[cur1] b[cur2]) ans ;std::cout ans \n;
}
signed main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t 1;while(t --) {solve();}return 0;
}
