Count on a Tree II

题目描述

You are given a tree with $N$ nodes. The tree nodes are numbered from $1$ to $N$. Each node has an integer weight.
We will ask you to perform the following operation:

  • $u$ $v$: ask for how many different integers that represent the weight of nodes there are on the path from $u$ to $v$.

题意概述

给定一棵$N$个节点的树,每个节点都有权值。有$M$次询问,每次询问给出$u, v$,求从$u$到$v$的路径上有多少种不同的权值。
数据范围:$1 \le N \le 40000, \; 1 \le M \le 10^5$。

算法分析

统计权值种类数,容易想到莫队,但这是在一棵树上,所以需要稍微做些转化。
求出树的括号序(DFS,访问和离开节点时均记录),那么每个询问都可以转化为对括号序上某个区间的询问。但是,如果区间内的某个节点出现了两次,那么这个节点不应该对答案产生贡献。因此,算法执行时可以用两个数组维护,一个表示节点的出现次数,另一个表示权值的出现次数。
具体来讲,令$s_i, e_i$分别表示访问、离开节点$i$的时间。假设$s_u \le s_v$。若$u$是$v$祖先,那么就相当于询问区间$[s_u, s_v]$;否则,相当于询问区间$[e_u, s_v]$,但此时$u, v$的LCA并没有被计算到答案中,因此需要把它加上。

代码

/*
 * Trap full -- please empty.
 */

#include <map>
#include <cstdio>
#include <cstring>
#include <algorithm>

template <typename T>
void read(T &n) {
  char c; for (; (c = getchar()) < '0' || c > '9'; ) ;
  for (n = c - '0'; (c = getchar()) >= '0' && c <= '9'; (n *= 10) += c - '0') ;
}

typedef int const ic;
typedef long long ll;

static ic N = 40005;
static ic M = 100005;
static ic K = 300;
std::map <int, int> num;
int nume, h[N], w[N], base[N], seq[N << 1];
int tim, st[N], ed[N], dep[N], up[N][16];
int mans, ml, mr, mvis[N], mrec[N], ans[M];
struct Edge {
  int v, nxt;
} e[N << 1];
struct Query {
  int l, r, lca, id;
  bool operator < (const Query &q) const {
    return l / K == q.l / K ? r < q.r : l / K < q.l / K;
  }
} q[M];

void add_edge(ic &u, ic &v) {
  e[++ nume] = (Edge) { v, h[u] }, h[u] = nume;
  e[++ nume] = (Edge) { u, h[v] }, h[v] = nume;
}

void dfs(ic &t, ic &fa) {
  seq[st[t] = ++ tim] = t, dep[t] = dep[fa] + 1, up[t][0] = fa;
  for (int i = h[t]; i; i = e[i].nxt)
    if (e[i].v != fa) dfs(e[i].v, t);
  seq[ed[t] = ++ tim] = t;
}

int get_lca(int u, int v) {
  if (dep[u] > dep[v]) std::swap(u, v);
  for (int i = 15; ~ i; -- i)
    if (dep[up[v][i]] >= dep[u]) v = up[v][i];
  if (u == v) return u;
  for (int i = 15; ~ i; -- i)
    if (up[u][i] != up[v][i]) u = up[u][i], v = up[v][i];
  return up[u][0];
}

void add(ic &u) {
  if (mvis[u]) {
    -- mrec[w[u]], mvis[u] = 0;
    if (! mrec[w[u]]) -- mans;
  } else {
    if (! mrec[w[u]]) ++ mans;
    ++ mrec[w[u]], mvis[u] = 1;
  }
}

void get(ic &l, ic &r) {
  for (; ml < l;) add(seq[ml ++]);
  for (; ml > l;) add(seq[-- ml]);
  for (; mr < r;) add(seq[++ mr]);
  for (; mr > r;) add(seq[mr --]);
}

int main() {
  int n, m; read(n), read(m);
  for (int i = 1; i <= n; ++ i) {
    read(w[i]);
    if (! num.count(w[i])) num[w[i]] = num.size();
    w[i] = num[w[i]];
  }
  for (int i = 1, u, v; i < n; ++ i) read(u), read(v), add_edge(u, v);
  dfs(1, 0);
  for (int i = 1; i < 16; ++ i)
    for (int j = 1; j <= n; ++ j) up[j][i] = up[up[j][i - 1]][i - 1];
  for (int i = 1, u, v; i <= m; ++ i) {
    read(u), read(v), q[i].id = i;
    if (st[u] > st[v]) std::swap(u, v);
    if (ed[u] > ed[v]) q[i].l = st[u] + 1, q[i].r = st[v], q[i].lca = u;
    else q[i].l = ed[u], q[i].r = st[v], q[i].lca = get_lca(u, v);
  }
  std::sort(q + 1, q + m + 1);
  mans = ml = mr = mvis[1] = mrec[w[1]] = 1;
  for (int i = 1; i <= m; ++ i) get(q[i].l, q[i].r), add(q[i].lca), ans[q[i].id] = mans, add(q[i].lca);
  for (int i = 1; i <= m; ++ i) printf("%d\n", ans[i]);
  return 0;
}

Bridges Painting

题目描述

New Berland consists of $N$ islands, some of them are connected by bridges. There can be no more than one bridge between any pair of islands. Mr. President issued a law to paint all bridges. A bridge can be painted white or black. Any island must have at least one white bridge and at least one black (of course if an island has more than one bridge).

题意概述

给定一张图,要求将所有边染成黑白两种颜色,使得每个度数大于$1$的点的连边都至少有一条黑色和一条白色。
数据范围:$1 \le N \le 100$。

算法分析

显然,我们可以分别考虑每个连通块。如果某个连通块仅由一个奇环构成,则不存在合法方案;否则,在连通块内任选一个度数不为$2$的点,从它开始进行交错染色(DFS);如果所有点的度数均为$2$,则任选一个点开始进行交错染色,再检验合法性。证明如下:

考虑DFS的过程。如果DFS经过一个点(进入并出去),根据交错染色的原则,入边和出边的颜色一定不相同。对于连通块内某个度数为$1$的点,它的连边可以任意染色;而对于度数大于$2$的点,如果从它开始DFS,则一定会再经过这个点至少一次。

由此得证。

代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct IOManager {
  template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); }
  inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; }
  inline int read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return 0; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', len); }
  template <typename T> inline IOManager operator > (T &x) { read(x); return *this; }
  template <typename T> inline void write(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); }
  inline void write(char c) { putchar(c); }
  inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); }
  template <typename T> inline IOManager operator < (T x) { write(x); return *this; }
} io;

struct Solver {
private:
  static const int N = 110;
  int n, col[N][N];
  vector <int> mp[N];
  void input() {
    io > n;
    for (int i = 1; i <= n; ++ i) {
      int t; io > t;
      while (t) mp[i].push_back(t), io > t;
    }
  }
  void dfs(int t, int c) {
    for (int i = 0; i < mp[t].size(); ++ i)
      if (! col[t][mp[t][i]]) col[t][mp[t][i]] = col[mp[t][i]][t] = c, dfs(mp[t][i], c = 3 - c);
  }
  void process() {
    for (int i = 1; i <= n; ++ i) if (mp[i].size() != 2) dfs(i, 1);
    for (int i = 1; i <= n; ++ i) dfs(i, 1);
    for (int i = 1; i <= n; ++ i) {
      bool w = false, b = false;
      for (int j = 0; j < mp[i].size(); ++ j) w |= col[i][mp[i][j]] == 1, b |= col[i][mp[i][j]] == 2;
      if (mp[i].size() > 1 && ! (w && b)) { io < (char *) "No solution\n"; return; }
    }
    for (int i = 1; i <= n; ++ i) {
      for (int j = 0; j < mp[i].size(); ++ j) io < col[i][mp[i][j]] < ' ';
      io < 0 < '\n';
    }
  }

public:
  void solve() { input(), process(); }
} solver;

int main() {
  solver.solve();
  return 0;
}

Domino

题目描述

Dominoes – game played with small, rectangular blocks of wood or other material, each identified by a number of dots, or pips, on its face. The blocks usually are called bones, dominoes, or pieces and sometimes men, stones, or even cards.
The face of each piece is divided, by a line or ridge, into two squares, each of which is marked as would be a pair of dice…
The principle in nearly all modern dominoes games is to match one end of a piece to another that is identically or reciprocally numbered.
ENCYCLOPÆDIA BRITANNICA
Given a set of domino pieces where each side is marked with two digits from $0$ to $6$. Your task is to arrange pieces in a line such way, that they touch through equal marked sides. It is possible to rotate pieces changing left and right side.

题意概述

有$N$张多米诺骨牌,每张骨牌的两个面上各有一个数。现需将骨牌排成一条直线,且要求相邻骨牌上相邻的两个数相同。所有数字在$0$到$6$之间。给出一组方案。
数据范围:$1 \le N \le 100$。

算法分析

将$0$到$6$看成点,骨牌看成边,就变成了经典的欧拉路径问题。直接DFS即可。

代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct IOManager {
  template <typename T>
  inline bool read(T &x) {
    char c; bool flag = false; x = 0;
    while (~ c && ! isdigit(c = getchar()) && c != '-') ;
    c == '-' && (flag = true, c = getchar());
    if (! ~ c) return false;
    while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return (flag && (x = -x), true);
  }
  inline bool read(char &c) {
    c = '\n';
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    return ~ c;
  }
  inline int read(char s[]) {
    char c; int len = 0;
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    if (! ~ c) return 0;
    while (isprint(c) && c != ' ') s[len ++] = c, c = getchar();
    return (s[len] = '\0', len);
  }
  template <typename T>
  inline IOManager operator > (T &x) {
    read(x); return *this;
  }
  template <typename T>
  inline void write(T x) {
    x < 0 && (putchar('-'), x = -x);
    x > 9 && (write(x / 10), true);
    putchar(x % 10 + '0');
  }
  inline void write(char c) {
    putchar(c);
  }
  inline void write(char s[]) {
    int pos = 0;
    while (s[pos] != '\0') putchar(s[pos ++]);
  }
  template <typename T>
  inline IOManager operator < (T x) {
    write(x); return *this;
  }
} io;

struct Solver {
private:
  static const int N = 110;
  static const int C = 10;
  int n, cnt, mp[C][C], in[C];
  bool vis[N];
  pair <int, int> line[N];
  vector <pair <int, int> > ans;
  void input() {
    io > n;
    for (int i = 1; i <= n; ++ i) {
      io > line[i].first > line[i].second;
      ++ mp[line[i].first][line[i].second], ++ mp[line[i].second][line[i].first];
      ++ in[line[i].first], ++ in[line[i].second];
    }
  }
  void dfs(int t) {
    for (int i = 0; i < C; ++ i)
      if (mp[t][i]) -- mp[t][i], --mp[i][t], dfs(i), ++ cnt, ans.push_back(make_pair(t, i));
  }
  void process() {
    cnt = 0; int s = -1;
    for (int i = 0; i < C; ++ i)
      if (in[i] & 1) ++ cnt, s = i;
      else if (in[i] && ! ~ s) s = i;
    if (cnt > 2) io < (char *) "No solution\n";
    else {
      cnt = 0, dfs(s);
      if (cnt < n) io < (char *) "No solution\n";
      else {
        for (int i = ans.size() - 1; ~ i; -- i)
          for (int j = 1; j <= n; ++ j)
            if (! vis[j]) {
              if (line[j].first == ans[i].first && line[j].second == ans[i].second) {
                io < j < ' ' < '+' < '\n', vis[j] = true; break;
              }
              if (line[j].first == ans[i].second && line[j].second == ans[i].first) {
                io < j < ' ' < '-' < '\n', vis[j] = true; break;
              }
            }
      }
    }
  }

public:
  void solve() { input(), process(); }
} solver;

int main() {
  solver.solve();
  return 0;
}

Cow Program

题目描述

Farmer John has just given the cows a program to play with! The program contains two integer variables, $x$ and $y$, and performs the following operations on a sequence $a_1, a_2, \ldots, a_n$ of positive integers:

  1. Initially, $x=1$ and $y=0$. If, after any step, $x \le 0$ or $x \gt n$, the program immediately terminates.
  2. The program increases both $x$ and $y$ by a value equal to $a_x$ simultaneously.
  3. The program now increases $y$ by $a_x$ while decreasing $x$ by $a_x$.
  4. The program executes steps 2 and 3 (first step 2, then step 3) repeatedly until it terminates (it may never terminate). So, the sequence of executed steps may start with: step 2, step 3, step 2, step 3, step 2 and so on.

The cows are not very good at arithmetic though, and they want to see how the program works. Please help them!
You are given the sequence $a_2, a_3, \ldots, a_n$. Suppose for each $i \; (1 \le i \le n-1)$ we run the program on the sequence $i, a_2, a_3, \ldots, a_n$. For each such run output the final value of $y$ if the program terminates or $-1$ if it does not terminate.

题意概述

有一个包含$n$个数的数列,第$i$项为$a_i$。现有两个数$x=1, \; y=0$。执行以下操作

while (!(x <= 0 || x > n)) {
  y += a[x], x += a[x];
  if (!(x <= 0 || x > n)) y += a[x], x -= a[x];
}

给定$a_2, a_3, \ldots, a_n$,对于所有$i \in [1, n-1]$,求对数列$i, a_2, a_3, \ldots, a_n$执行操作后$y$的值。若无限循环则输出$-1$。
数据范围:$2 \le n \le 2 \times 10^5, \; 1 \le a_i \le 10^9$。

算法分析

直接模拟肯定会超时。易知从一个位置开始执行操作的顺序是固定的,因此可以用记忆化搜索,记录下每一个位置向左或向右执行操作后的$y$值。如果搜索到一个已搜索过但还没有得到答案的位置,则返回$-1$。

代码

#include <iostream>
using namespace std;
long long n, a[300001], ans[300001][2], to[300001][2], vis[300001][2];
long long dfs(long long t, long long m) {
  if (ans[t][m]) return ans[t][m];
  if (vis[t][m]) return ans[t][m] = -1; vis[t][m] = true;
  if (to[t][m] < 1 || to[t][m] > n) return ans[t][m] = a[t];
  long long ret = dfs(to[t][m], !m);
  if (ret == -1) ans[t][m] = -1; else ans[t][m] = a[t] + ret;
  return ans[t][m];
}
int main()
{
  cin >> n, vis[1][1] = true;
  for (int i = 2; i <= n; ++i) cin >> a[i];
  for (int i = 2; i <= n; ++i) to[i][0] = i - a[i], to[i][1] = i + a[i];
  for (int i = 2; i <= n; ++i) if (!ans[i][0]) dfs(i, 0);
  for (int i = 1; i < n; ++i)
    if (ans[i + 1][0] == -1) cout << -1 << endl;
    else cout << i + ans[i + 1][0] << endl;
  return 0;
}

Petya and Tree

题目描述

One night, having had a hard day at work, Petya saw a nightmare. There was a binary search tree in the dream. But it was not the actual tree that scared Petya. The horrifying thing was that Petya couldn’t search for elements in this tree. Petya tried many times to choose key and look for it in the tree, and each time he arrived at a wrong place. Petya has been racking his brains for long, choosing keys many times, but the result was no better. But the moment before Petya would start to despair, he had an epiphany: every time he was looking for keys, the tree didn’t have the key, and occured exactly one mistake. “That’s not a problem!”, thought Petya. “Why not count the expectation value of an element, which is found when I search for the key”. The moment he was about to do just that, however, Petya suddenly woke up.
Thus, you are given a binary search tree, that is a tree containing some number written in the node. This number is called the node key. The number of children of every node of the tree is equal either to $0$ or to $2$. The nodes that have $0$ children are called leaves and the nodes that have $2$ children, are called inner. An inner node has the left child, that is the child whose key is less than the current node’s key, and the right child, whose key is more than the current node’s key. Also, a key of any node is strictly larger than all the keys of the left subtree of the node and strictly smaller than all the keys of the right subtree of the node.
Also you are given a set of search keys, all of which are distinct and differ from the node keys contained in the tree. For each key from the set its search in the tree is realised. The search is arranged like this: initially we are located in the tree root, if the key of the current node is larger that our search key, then we move to the left child of the node, otherwise we go to the right child of the node and the process is repeated. As it is guaranteed that the search key is not contained in the tree, the search will always finish in some leaf. The key lying in the leaf is declared the search result.
It is known for sure that during the search we make a mistake in comparing exactly once, that is we go the wrong way, but we won’t make any mistakes later. All possible mistakes are equiprobable, that is we should consider all such searches where exactly one mistake occurs. Your task is to find the expectation (the average value) of the search result for every search key, considering that exactly one mistake occurs in the search. That is, for a set of paths containing exactly one mistake in the given key search, you should count the average value of keys containing in the leaves of those paths.

题意概述

给定一棵包含$n$个节点的二叉搜索树,每个节点都有$0$个或$2$个儿子。如果一个节点有儿子,那么它左子树中的所有节点的值都严格小于这个节点,它右子树中的所有节点的值都严格大于这个节点。由于一些差错,这棵搜索树在查找一个值时总是会犯恰好一次错误——应该往左查找时却往右查找,应该往右查找时却往左查找。现有$k$个树中不存在的值待查找,求每一次查找得到的数的期望。
数据范围:$3 \le n \lt 10^5, \; 1 \le k \le 10^5$。

算法分析

很容易想到暴力的方法:先DFS预处理出每棵子树中的最大值和最小值,接着对于每一个待查找的值,直接在树中查找;若应该往左子树走,则将答案加上右子树中的最小值,否则加上左子树中的最大值,然后往正确的方向走。由于这并不是一棵平衡树,因此最坏情况的时间复杂度为$O(n^2)$。
搜索树中的数将数字划分成了$(n+1)$个区间。对于每一个区间而言,其答案都是一样的。因此,我们可以再进行一次DFS,处理出每个区间的答案。处理方法类似于暴力,但是搜索完一棵子树后需要回溯。最后查找$k$个数时,只需对每个数二分查找属于哪个区间,并输出那个区间的答案。

代码

#include <cstdio>
#include <algorithm>
using namespace std;
struct node_type {
  long long val, min, max, child[2];
} node[100001];
long long n, k, cnt, times, root, top, id[100001];
double ans[100001];
void dfs(long long t) {
  if (!node[t].child[0]) {
    node[t].min = node[t].max = node[t].val; return;
  }
  dfs(node[t].child[0]), dfs(node[t].child[1]);
  node[t].min = node[node[t].child[0]].min, node[t].max = node[node[t].child[1]].max;
}
void find(long long t) {
  if (!node[t].child[0]) {
    id[top] = node[t].val, ans[top++] = 1.0 * cnt / times; return;
  }
  cnt += node[node[t].child[1]].min, ++times, find(node[t].child[0]), id[top++] = node[t].val;
  cnt += node[node[t].child[0]].max - node[node[t].child[1]].min, find(node[t].child[1]);
  cnt -= node[node[t].child[0]].max, --times;
}
int main()
{
  scanf("%lld", &n);
  for (int i = 1; i <= n; ++i) {
    long long a; scanf("%lld%lld", &a, &node[i].val);
    if (a == -1) root = i;
    else if (!node[a].child[0]) node[a].child[0] = i;
      else {
        node[a].child[1] = i;
        if (node[node[a].child[0]].val > node[node[a].child[1]].val)
          node[a].child[0] ^= node[a].child[1] ^= node[a].child[0] ^= node[a].child[1];
      }
  }
  dfs(root), find(root), scanf("%lld", &k);
  for (int i = top - 2; i >= 0; --i) if (!ans[i]) ans[i] = ans[i + 1];
  while (k--) {
    long long a, l = 0, r = top; scanf("%lld", &a);
    while (l + 1 < r) {
      long long mid = l + r >> 1; if (id[mid] < a) l = mid; else r = mid;
    }
    printf("%.10lf\n", ans[l]);
  }
  return 0;
}