1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

#include <iostream>
using namespace std;

int t,x,y,n;

int main(){
    scanf("%d\n",&t);
    while(t--){
        scanf("%d\n",&n);
        for(int i=1;i<n;i++)
            scanf("%d %d",&x,&y);
        if(n%2==1)
            puts("Alice");
        else
        {
            puts("Bob");
        }

    }
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120

#include <bits/stdc++.h>
using namespace std;

// #define debug(...) fprintf(stderr, __VA_ARGS__)
#define debug(...)

typedef long long ll;
const int MAXN = 2e5 + 5;

template <typename T> void cmax(T &a, T b) { (a < b) && (a = b); }

bitset<MAXN> vis;
vector<int> adj[MAXN];
int a[MAXN], f[MAXN], sz[MAXN], root, n, all;
ll ans;

void getRoot(int u, int from) {
  sz[u] = 1, f[u] = 0;
  for (int v : adj[u]) {
    if (vis[v] || v == from) continue;
    getRoot(v, u);
    sz[u] += sz[v];
    cmax(f[u], sz[v]);
  }
  cmax(f[u], all - sz[u]);
  if (f[u] < f[root]) root = u;
}

int cnt;
pair<ll, int> segment[MAXN];
pair<int, int> single[MAXN];
void dfs(int u, int from, int max_value, ll sum) {
  single[++cnt].first = max_value;
  segment[cnt] = make_pair(sum, cnt);
  for (int v : adj[u]) {
    if (vis[v] || v == from) continue;
    dfs(v, u, max(max_value, a[v]), sum + a[v]);
  }
}

int tree[MAXN];
void add(int x) {
  for (; x <= cnt; x += x & -x) ++tree[x];
}
int ask(int x) {
  int res = 0;
  for (; x; x &= x - 1) res += tree[x];
  return res;
}

ll gao(int u, int val) {
  cnt = 0;
  dfs(u, 0, max(val, a[u]), val + a[u]);
  int head = val ? val : a[u];
  sort(segment + 1, segment + cnt + 1);
  for (int i = 1; i <= cnt; ++i) single[segment[i].second].second = i;
  sort(single + 1, single + cnt + 1);
  memset(tree + 1, 0, cnt * sizeof(int));
  ll res = 0;
  for (int i = 1; i <= cnt; ++i) {
    int left = 1, right = cnt, idx = 0;
    ll bound = 2ll * single[i].first - segment[single[i].second].first + head;
    while (left <= right) {
      int mid = (left + right) / 2;
      if (segment[mid].first <= bound) {
        idx = mid;
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
    res += i - 1 - ask(idx);
    add(single[i].second);
  }
  debug("# %d %d %lld\n", u, val, res);
  return res;
}

void solve(int u) {
  all = f[0] = sz[u];
  getRoot(u, root = 0);
  vis[root] = true;
  ans += gao(root, 0);
  for (int v : adj[root]) {
    if (vis[v]) continue;
    ans -= gao(v, a[root]);
  }
  for (int v : adj[root]) {
    if (vis[v]) continue;
    solve(v);
  }
}

void solveCase() {
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    adj[i].clear();
    vis[i] = false;
  }
  for (int i = 1, u, v; i < n; ++i) {
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  for (int i = 1; i <= n; ++i) reverse(adj[i].begin(), adj[i].end());
  ans = 0, sz[1] = n;
  solve(1);
  cout << ans << "\n";
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);

  int o_o;
  for (cin >> o_o; o_o; --o_o) solveCase();

  return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#include <bits/stdc++.h>
using namespace std;

void solve() {
  int k, x;
  cin >> k >> x;
  vector<int> dig;
  for (; x; x /= k) dig.push_back(x % k);
  int n = dig.size();
  for (int i = 0; i < n - 1; ++i) {
    if (dig[i] > 0) continue;
    dig[i] += k, --dig[i + 1];
  }
  while (dig[n - 1] == 0) --n;
  for (int i = n - 1; ~i; --i) cout << dig[i] + 9 - k;
  cout << "\n";
}

int main(int argc, char *argv[]) {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  cout << fixed << setprecision(10);

  int o_o;
  for (cin >> o_o; o_o; --o_o) solve();
  return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;

#define rep(i, a, b) for (int i = a; i <= b; i++)
#define dep(i, a, b) for (int i = a; i >= b; i--)
#define fill(a, x) memset(a, x, sizeof(a))

const int N = 100000 + 5;
const int INF = 10000;

typedef long long ll;

int k, cnt;
int fa[N];
int w[N];


int dfs(int k, int x) {
    if (k == 0) return 0;
    if (k == 1) return w[x] = 1;
    int leaf_sum;
    bool flag = false;
    if (k & 1) {
        flag = true;
        k--;
    }
    // else {
    cnt++;
    fa[cnt] = x;
    w[cnt] = 1;

    cnt++;
    fa[cnt] = cnt - 1;
    w[cnt] = 1;

    cnt++;
    fa[cnt] = x;
    leaf_sum = dfs(k >> 1, cnt) + 1;
    w[x] = flag ? leaf_sum : INF;
    // }
    return leaf_sum;
}

int main()
{
    #ifndef ONLINE_JUDGE
        freopen("g.in", "r", stdin);
    #endif

    scanf("%d", &k);
    if (k == 1) {
        puts("2\n1\n5000 1");
        return 0;
    }
    cnt = 1;
    fill(w, -1);
    dfs(k, 1);
    printf("%d\n", cnt);
    rep(i, 2, cnt - 1) printf("%d ", fa[i]);
    printf("%d", fa[cnt]);
    puts("");
    rep(i, 1, cnt - 1) printf("%d ", w[i]);
    printf("%d\n", w[cnt]);
    return 0;
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5e5 + 3;
const int MAXM = 1e6 + 3;
const int INF = 0x3f3f3f3f;

vector<int> stks[MAXM * 4];
vector<tuple<int, int, int>> qs[MAXN];
int n, m, h[MAXN], v[MAXN], ans[MAXM], heights[MAXM];

void clear_tree(int u, int l, int r) {
  stks[u].clear();
  if (l == r) return;
  int mid = (l + r) / 2;
  clear_tree(u << 1, l, mid);
  clear_tree(u << 1 | 1, mid + 1, r);
}

void insert(int u, int l, int r, int x) {
  auto &stk = stks[u];
  while (stk.size() && v[stk.back()] >= v[x]) stk.pop_back();
  stk.push_back(x);
  if (l == r) return;
  int mid = (l + r) / 2;
  if (h[x] <= mid) {
    insert(u << 1, l, mid, x);
  } else {
    insert(u << 1 | 1, mid + 1, r, x);
  }
}

bool check(const vector<int> &stk, int left, int time) {
  for (int l = 0, r = stk.size() - 1; l <= r;) {
    int mid = (l + r) / 2;
    if (stk[mid] >= left && v[stk[mid]] <= time) return true;
    stk[mid] >= left ? r = mid - 1 : l = mid + 1;
  }
  return false;
}

int q_max(int u, int l, int r, int left, int height, int time) {
  auto &stk = stks[u];
  if (stk.empty() || v[stk[0]] > time) return -1;
  if (l == r) return l <= height && check(stk, left, time) ? l : -1;
  if (r <= height && !check(stk, left, time)) return -1;
  int mid = (l + r) / 2;
  if (height > mid) {
    int temp = q_max(u << 1 | 1, mid + 1, r, left, height, time);
    if (~temp) return temp;
  }
  return q_max(u << 1, l, mid, left, height, time);
}

int q_min(int u, int l, int r, int left, int height, int time) {
  auto &stk = stks[u];
  if (stk.empty() || v[stk[0]] > time) return -1;
  if (l == r) return l >= height && check(stk, left, time) ? l : -1;
  if (l >= height && !check(stk, left, time)) return -1;
  int mid = (l + r) / 2;
  if (height <= mid) {
    int temp = q_min(u << 1, l, mid, left, height, time);
    if (~temp) return temp;
  }
  return q_min(u << 1 | 1, mid + 1, r, left, height, time);
}

void solve() {
  int tot = 0;
  cin >> n >> m;
  memset(h + 1, 0, sizeof(int) * n);
  memset(ans, 0x3f, sizeof(int) * m);

  for (int i = 0, opt, a, b, c; i < m; ++i) {
    cin >> opt >> a >> b;
    if (opt) {
      cin >> c;
      heights[tot++] = c;
      qs[b].emplace_back(a, c, i);
    } else {
      heights[tot++] = b;
      h[a] = b, v[a] = i;
    }
  }

  sort(heights, heights + tot);
  tot = unique(heights, heights + tot) - heights;

  static auto gid = [&](int x) {
    return lower_bound(heights, heights + tot, x) - heights;
  };

  clear_tree(1, 0, tot - 1);
  for (int r = 1; r <= n; ++r) {
    if (h[r]) h[r] = gid(h[r]), insert(1, 0, tot - 1, r);
    for (auto tp : qs[r]) {
      int l, height, id, temp;
      tie(l, height, id) = tp;
      height = gid(height);
      // cerr << "# " << height << "\n";
      temp = q_max(1, 0, tot - 1, l, height, id);
      // cerr << "# " << temp << "\n";
      if (~temp) ans[id] = heights[height] - heights[temp];
      temp = q_min(1, 0, tot - 1, l, height, id);
      // cerr << "# " << temp << "\n";
      if (~temp) ans[id] = min(ans[id], heights[temp] - heights[height]);
      if (ans[id] == INF) ans[id] = -1;
    }
    qs[r].clear();
  }

  for (int i = 0; i < m; ++i) {
    if (ans[i] == INF) continue;
    cout << ans[i] << "\n";
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);

  int o_o;
  for (cin >> o_o; o_o; --o_o) solve();
  return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5 + 3;

int k[MAXN], q[MAXN][3];
long long took[MAXN],  pre[MAXN][3], goal[MAXN];

priority_queue<pair<long long, int>> heap[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    int n, m, opt, x, y, last = 0, idx = 0;
    for (cin >> n >> m; m; --m) {
        cin >> opt;
        if (opt == 1) {
            x = ++idx;
            cin >> goal[x] >> k[x];
            goal[x] ^= last;
            for (int i = 0; i < k[x]; ++i) {
                cin >> q[x][i];
                q[x][i] ^= last;
                pre[x][i] = took[q[x][i]];
                heap[q[x][i]].emplace(
                       -took[q[x][i]] - (goal[x] + k[x] - 1) / k[x], x);
            }
        } else {
            cin >> x >> y;
            x ^= last, y ^= last;

            took[x] += y;
            auto &h = heap[x];
            static int ans[MAXN];
            static bitset<MAXN> mark;
            static auto gao = [&](int x) {
                if (mark[x]) return;
                for (int i = 0; i < k[x]; ++i) {
                    goal[x] -= took[q[x][i]] - pre[x][i];
                    pre[x][i] = took[q[x][i]];
                }
                if (goal[x] <= 0) {
                    mark[x] = 1;
                    ans[last++] = x;
                } else {
                    for (int i = 0; i < k[x]; ++i)
                        heap[q[x][i]].emplace(
                            -took[q[x][i]] - (goal[x] + k[x] - 1) / k[x], x);
                }
            };

            last = 0;
            while (!h.empty()) {
                auto p = h.top();
                if (p.first + took[x] < 0) break;
                h.pop();
                gao(p.second);
            }


            sort(ans, ans + last);
            cout << last;
            for (int i = 0; i < last; ++i) cout << " " << ans[i];
            cout << "\n";
        }
    }

    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5000 + 3;
const int MAXM = 60;
const int MOD = 1e9 + 7;

int f[MAXN][MAXM][MAXM], mark[MAXN][MAXM][MAXM], clk, dig[MAXN], p[MAXN], m;

int gao(int pos, int sum, int delta, bool limit) {
    if (pos < 0) return delta == 0;
    if (!limit && mark[pos][sum][delta] == clk) return f[pos][sum][delta];
    int res = 0, bound = limit ? dig[pos] : 9;
    for (int i = 0; i <= bound; ++i) {
        int sum_ = (sum + i) % m;
        int delta_ = (delta + i * p[pos] - i * sum) % m;
        if (delta_ < 0) delta_ += m;
        res += gao(pos - 1, sum_, delta_, limit && i == bound);
        if (res >= MOD) res -= MOD;
    }
    if (!limit) f[pos][sum][delta] = res, mark[pos][sum][delta] = clk;
    return res;
}

char L[MAXN], R[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    int o_o;
    for (cin >> o_o; o_o; --o_o) {
        ++clk;
        cin >> L >> R >> m;
        int n = strlen(R);
        for (int i = p[0] = 1; i < n; ++i) p[i] = p[i - 1] * 10 % m;

        for (int i = 0; i < n; ++i) dig[i] = R[n - 1 - i] - '0';
        int ans = gao(n - 1, 0, 0, true);
        // cerr << "# " << ans << "\n";

        n = strlen(L);
        for (int i = 0; i < n; ++i) dig[i] = L[n - 1 - i] - '0';
        --dig[0];
        for (int i = 0; dig[i] < 0; ++i) {
            --dig[i + 1], dig[i] += 10;
        }
        while (!dig[n - 1]) --n;
        ans -= gao(n - 1, 0, 0, true);
        // cerr << "# " << ans << "\n";
        if (ans < 0) ans += MOD;
        cout << ans << "\n";
    }

    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 800 + 3;
const int INF = 0x3f3f3f3f;

int n, m, d[MAXN], flow[MAXN];
vector<int> algos[MAXN], softs[MAXN];

int gao(int x) { return x >= INF ? INF : x; }

int lr_solve(int &x, int &y) {
  int now = algos[1].empty() ? INF : algos[1].back();
  int cost = gao(now + (softs[1].empty() ? INF : softs[1].back()));
  int link = x = y = 1;
  for (int i = 2; i <= n; ++i) {
    now = gao(now + (flow[i - 1] >= 0 ? d[i - 1] : -d[i - 1]));
    if (algos[i].size() && algos[i].back() < now) {
      link = i;
      now = algos[i].back();
    }
    if (softs[i].size() && gao(now + softs[i].back()) < cost) {
      x = link, y = i;
      cost = gao(now + softs[i].back());
    }
  }
  return cost;
}

int rl_solve(int &x, int &y) {
  int now = algos[n].empty() ? INF : algos[n].back();
  int cost = gao(now + (softs[n].empty() ? INF : softs[n].back()));
  int link = x = y = n;
  for (int i = n - 1; i >= 1; --i) {
    now = gao(now + (flow[i] <= 0 ? d[i] : -d[i]));
    if (algos[i].size() && algos[i].back() < now) {
      link = i;
      now = algos[i].back();
    }
    if (softs[i].size() && gao(now + softs[i].back()) < cost) {
      x = link, y = i;
      cost = gao(now + softs[i].back());
    }
  }
  return cost;
}

int main() {
  ios::sync_with_stdio(false);

  cin >> n >> m;
  for (int i = 1; i < n; ++i) cin >> d[i];
  for (int i = 0, x, c; i < m; ++i) {
    cin >> x >> c;
    algos[x].push_back(c);
  }
  for (int i = 0, x, c; i < m; ++i) {
    cin >> x >> c;
    softs[x].push_back(c);
  }
  for (int i = 1; i <= n; ++i) {
    sort(algos[i].begin(), algos[i].end(), greater<int>());
    sort(softs[i].begin(), softs[i].end(), greater<int>());
  }

  long long ans = 0;
  for (int i = 0; i < m; ++i) {
    int x1, x2, y1, y2, ans1, ans2;
    ans1 = lr_solve(x1, y1);
    ans2 = rl_solve(x2, y2);
    if (ans1 <= ans2) {
      ans += ans1;
      algos[x1].pop_back();
      softs[y1].pop_back();
      for (int i = x1; i < y1; ++i) ++flow[i];
    } else {
      ans += ans2;
      algos[x2].pop_back();
      softs[y2].pop_back();
      for (int i = y2; i < x2; ++i) --flow[i];
    }
    cout << ans << "\n";
  }

  return 0;
}