C Cut
我的质因数分解不是在杨老师这里学的，所以我写挂了，杨老师好闪拜谢杨老师
#include <iostream>
#define int long longusing namespace std;const int MaxN = 1e5 + 10;int f[MaxN][20], mn[MaxN][20], nxt[MaxN], pri[MaxN], a[MaxN], p[MaxN], tot, n, q;
bool vis[MaxN];int qmn(int x, int len, int res = 1e9) {for (int i = 19; i >= 0; i--) {if (len & (1 << i)) {res = min(res, mn[x][i]), x += (1 << i);}}return res;
}int GO(int x, int len) {for (int i = 19; i >= 0; i--) {if (len & (1 << i)) {x = f[x][i];}}return x;
}signed main() {ios::sync_with_stdio(0), cin.tie(0);cin >> n >> q;for (int i = 1; i <= n; i++) {cin >> a[i];}for (int i = 1; i < MaxN; i++) {nxt[i] = n + 1;}for (int i = n; i >= 1; i--) {p[i] = n + 1;for (int j = 2; j * j <= a[i]; j++) {if (a[i] % j == 0) {p[i] = min(p[i], nxt[j]), nxt[j] = i;while (a[i] % j == 0) {a[i] /= j; }}}if (a[i] > 1) p[i] = min(p[i], nxt[a[i]]), nxt[a[i]] = i;mn[i][0] = p[i];}for (int i = 1; i <= 19; i++) {for (int j = 1; j + (1 << i) - 1 <= n; j++) {mn[j][i] = min(mn[j][i - 1], mn[j + (1 << (i - 1))][i - 1]);}}for (int i = 1; i <= n; i++) {f[i][0] = qmn(i, p[i] - 1 - i + 1);}f[n + 1][0] = n + 1;for (int i = 1; i <= 19; i++) {for (int j = 1; j <= n + 1; j++) {f[j][i] = f[f[j][i - 1]][i - 1];}}for (int u, v, l, r; q; q--) {cin >> u >> v, l = 0, r = MaxN - 1;while (l < r) {int mid = l + r >> 1;GO(u, mid) > v ? r = mid : l = mid + 1; }cout << l << '\n';}return 0;
}
D Distinctive Roots in a Tree
我被误导了，我以为是用相等的颜色就将路径标记，但是由于这个会有多个相等的所以不能做。
我们从整体到个体来思考，我们考虑单个点，他如果儿子的某一个子树内有和它相同的，那么这个子树外面的都要标记为不可能。
如果当前点子树外有和它相同的，那么子树内的都要标记为不可能。
#include <iostream>
#include <vector>
#include <map>using namespace std;const int MaxN = 2e5 + 10;int dfn[MaxN], sz[MaxN], sum[MaxN], d[MaxN], id, a[MaxN], n;
vector<int> g[MaxN];
map<int, int> cnt, tot;void DFS(int x, int fa = 0) {dfn[x] = ++id;int pre = cnt[a[x]];cnt[a[x]]++, sz[x] = 1;for (int i : g[x]) {if (i == fa) continue;int tmp = cnt[a[x]];DFS(i, x); sz[x] += sz[i];if (tmp != cnt[a[x]]) {d[1]++, d[dfn[i]]--, d[dfn[i] + sz[i]]++;}}if (cnt[a[x]] - pre < tot[a[x]]) {d[dfn[x]]++, d[dfn[x] + sz[x]]--;}
}int main() {cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i], tot[a[i]]++;}for (int i = 1, u, v; i < n; i++) {cin >> u >> v;g[u].push_back(v), g[v].push_back(u);}DFS(1);for (int i = 1; i <= n; i++) {d[i] += d[i - 1];d[0] += !d[i];}cout << d[0] << '\n';return 0;
}