## 题目描述

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$.

## 代码

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

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

template <typename T>
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];
}

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() {
for (int i = 1; i <= n; ++ i) {
if (! num.count(w[i])) num[w[i]] = num.size();
w[i] = num[w[i]];
}
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) {
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;
}


## 题目描述

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).

## 代码

#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;
}


## 题目描述

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.

## 代码

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

using namespace std;

struct IOManager {
template <typename T>
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);
}
c = '\n';
while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
return ~ c;
}
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) {
}
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;
}


## 题目描述

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.

## 题意概述

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


## 代码

#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;
}


## 题目描述

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.

## 代码

#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;
}