国庆集训1021-1022（未完成）

DOVO的疑惑

#include<bits/stdc++.h>
#define ll long long
using namespace std;ll m, ans = 1, sum=1, n;
ll gcd(ll a, ll b) {
     return !b ? a : gcd(b, a%b); }
ll lcm(ll a, ll b) {
     return a/gcd(a, b)*b; }int main() {
    scanf("%lld", &n);for(int i = 1; i <= n; i++) {
    scanf("%lld", &m);ans = ans*m;sum = lcm(sum, m);}printf("%lld\n", ans-sum);return 0;
}

捉迷藏

92分贪心算法（不知道错在哪里……QAQ）
#include<bits/stdc++.h>
#define ll long long
using namespace std;const int M = 1e6+10;
struct psx{
    int next, y;} e[2*M];
int lin[M], a[M], f[M]={
    },ai[M], son[M]={
    }, len=0, cnt=0, n, minn, id, sun=0;
bool vis[M]={
    };void insert(int xx, int yy) {
    e[++len].next = lin[xx];lin[xx] = len;e[len].y = yy;
}void work1(int k) {
    vis[k] = 1;if(!a[k]) {
     f[k] = 0; return; }cnt++;ai[++len] = k;for(int i = lin[k]; i; i = e[i].next) if(!vis[e[i].y]) work1(e[i].y); 
}void work2(int k) {
    son[k] = 1; vis[k] = 1;for(int i = lin[k]; i ; i = e[i].next) if(!vis[e[i].y]) {
    work2(e[i].y);son[k] += son[e[i].y];}
}void work3(int k, int num) {
    vis[k] = 1;for(int i = lin[k]; i ; i = e[i].next)if(!vis[e[i].y]) {
    f[e[i].y] = num;work3(e[i].y, num);}
}void work4(int k) {
    minn = n;for(int i = 1; i <= n; i++) if(!a[i] && son[i] < minn)minn = son[i];for(int i = 1; i <= sun; i++)f[ai[i]] = max(f[ai[i]], n-minn);
}void work6(int k) {
    vis[k] = 1;ai[++sun] = k;for(int i = lin[k]; i ; i = e[i].next) if(!vis[e[i].y] && ((k==id) && (son[e[i].y]<son[k]) || k != id)) {
    work6(e[i].y);f[e[i].y] = minn;}
}void work5() {
    for(int i = 1; i <= n; i++) if(a[i]) {
     work2(i); break;}minn = n;bool fla = 0;for(int i = 1; i <= n; i++) {
    if(!a[i] && min(son[i]-1, n-son[i]) == minn)fla = 1;if(!a[i] && min(son[i]-1, n-son[i]) < minn) id = i, minn = min(son[i]-1, n-son[i]), fla = 0;}for(int i = 1; i <= n; i++)f[i] = n-minn-1;if(fla) return;f[id] = 0;memset(vis, 0, sizeof(vis));work6(id);memset(vis, 0, sizeof(vis));work2(id);memset(vis, 0, sizeof(vis));work4(id);
}int main() {
    scanf("%d", &n);for(int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);if(!a[i]) cnt++;}for(int i = 1; i < n; i++) {
    int v, u;scanf("%d%d", &u, &v);insert(u, v);insert(v, u);}if(!(cnt&1)) {
    for(int i = 1; i <= n; i++)printf("%d\n", n);return 0;}else if(cnt == 1) {
    for(int i = 1; i <= n; i++) if(!vis[i]) {
    cnt = 0, len = 0, work1(i);for(int j = 1; j <= len; j++) f[ai[j]] = cnt;}for(int i = 1; i <= n; i++)printf("%d\n", f[i]);return 0;}else if(cnt == n) {
    for(int i = 1; i <= n; i++)printf("%d\n", n-1);return 0;}else {
    work5();for(int i = 1; i <= n; i++)printf("%d\n", f[i]);}return 0;
}