Codeforces 463E Caisa and Tree

Caisa and Tree

在dfs的过程中枚举质因子瞎搞搞就好啦， 不过这个题意真的表述不清。。

#include<bits/stdc++.h> #define LL long long #define fi first #define se second #define mk make_pair #define PLL pair<LL, LL> #define PLI pair<LL, int> #define PII pair<int, int> #define SZ(x) ((int)x.size()) #define ull unsigned long long using namespace std;const int N = 1e5 + 7; const int M = 2e6 + 7; const int inf = 0x3f3f3f3f; const LL INF = 0x3f3f3f3f3f3f3f3f; const int mod = 1e6 + 3; const double eps = 1e-8;int n, q, a[N], ans[N], depth[N]; bool prime[M]; vector<int> pfac[M]; vector<PII> Set[M]; vector<int> G[N];void dfs(int u, int fa) {depth[u] = depth[fa] + 1;ans[u] = -1;for(auto& t : pfac[a[u]])if(SZ(Set[t]) && (ans[u] == -1 || Set[t][SZ(Set[t])-1].fi > depth[ans[u]]))ans[u] = Set[t][SZ(Set[t])-1].se;for(auto& t : pfac[a[u]])Set[t].push_back(mk(depth[u], u));for(auto& v : G[u]) {if(v == fa) continue;dfs(v, u);}for(auto& t : pfac[a[u]])Set[t].pop_back(); }int main() {memset(prime, true, sizeof(prime));prime[0] = prime[1] = false;for(int i = 2; i < M; i++) {if(!prime[i]) continue;pfac[i].push_back(i);for(int j = i + i; j < M; j += i)prime[j] = false, pfac[j].push_back(i);}scanf("%d%d", &n, &q);for(int i = 1; i <= n; i++) scanf("%d", &a[i]);for(int i = 1; i < n; i++) {int u, v; scanf("%d%d", &u, &v);G[u].push_back(v);G[v].push_back(u);}dfs(1, 0);while(q--) {int op, v, w;scanf("%d%d", &op, &v);if(op == 1) {printf("%d\n", ans[v]);} else {scanf("%d", &w);a[v] = w;dfs(1, 0);}}return 0; }/* */

 

转载于:https://www.cnblogs.com/CJLHY/p/10403544.html

总结

以上是生活随笔为你收集整理的Codeforces 463E Caisa and Tree的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。