Home » 国际竞赛 » Details

USACO 2019 December Contest, Gold Problem 2. Milk Visits

Category: 国际竞赛, 计算机国际竞赛 Date: 2022年7月1日下午3:21

USACO 2019 December Contest, Gold Problem 2. Milk Visits

Farmer John is planning to build $N$ ( $1 \leq N \leq 10^{5}$ ) farms that will be connected by $N - 1$ roads, forming a tree (i.e., all farms are reachable from each-other, and there are no cycles). Each farm contains a cow with an integer type $T_{i}$ between $1$ and $N$ inclusive.

Farmer John's $M$ friends ( $1 \leq M \leq 10^{5}$ ) often come to visit him. During a visit with friend $i$ , Farmer John will walk with his friend along the unique path of roads from farm $A_{i}$ to farm $B_{i}$ (it may be the case that $A_{i} = B_{i}$ ). Additionally, they can try some milk from any cow along the path they walk. Since most of Farmer John's friends are also farmers, they have very strong preferences regarding milk. Each of his friends will only drink milk from a certain type of cow. Any of Farmer John's friends will only be happy if they can drink their preferred type of milk during their visit.

Please determine whether each friend will be happy after visiting.

SCORING:

Test case 2 is the second example case below.
Test case 3 satisfies $N \leq 10^{3}, M \leq 2 \cdot 10^{3}$ .
Test cases 4-7 satisfy $C_{i} \leq 10$ ( $C_{i}$ defined below).

INPUT FORMAT (file milkvisits.in):

The first line contains two integer $N$ and $M$ .The second line contains $N$ space-separated integers $T_{1}, T_{2}, \dots, T_{N} .$ The type of the cow in the $i$ -th farm is denoted by $T_{i} .$

The next $N - 1$ lines each contain two distinct integers $X$ and $Y$ ( $1 \leq X, Y \leq N$ ), indicating that there is an edge between farms $X$ and $Y$ .

The next $M$ lines contain integers $A_{i}$ , $B_{i}$ , and $C_{i}$ . $A_{i}$ and $B_{i}$ represent the endpoints of the path walked during friend $i$ 's visit, while $C_{i}$ ( $1 \leq C_{i} \leq N$ ) indicates the type of cow whose milk the friend enjoys drinking.

OUTPUT FORMAT (file milkvisits.out):

Print a binary string of length $M .$ The $i$ th character of the string should be '1' if the $i$ th friend will be happy, or '0' otherwise.

SAMPLE INPUT:

SAMPLE OUTPUT:

In this example, the path from 1 and 4 involves farms 1, 2, and 4. All of these contain cows of type 1, so the first friend will be satisfied while the second one will not.

SAMPLE INPUT:

6 4
1 2 3 3 3 3
1 2
2 3
3 4
2 5
5 6
4 6 1
4 6 2
4 6 3
4 6 4

SAMPLE OUTPUT:

Problem credits: Spencer Compton

<h3> USACO 2019 December Contest, Gold Problem 2. Milk Visits 题解(翰林国际教育提供，仅供参考)</h3>
<p style="text-align: center;">题解请<a href="/register" target="_blank" rel="noopener">注册</a>或<a href="/login" target="_blank" rel="noopener">登录</a>查看</p>
[/hide]

(Analysis by Benjamin Qi)

We can answer the queries offline (meaning that we process them in an order that is convenient for us, not that which is given by the input). Like the silver version, run a DFS from farm $1$ . Suppose that we're currently processing the farm $x .$ Store a stack $o r d$ containing all the nodes on the path from $1$ to $x,$ and also a stack $s t o r [t]$ for each type $t$ containing the pairs $(y, d e p t h [y])$ for all farms $y$ with type $t$ on the path from $1$ to $x .$

Suppose that we want to update the answer for a query $i$ having an endpoint $A_{i} = x$ (the reasoning for $B_{i} = x$ is similar). We need to check whether the last farm $y$ in the stack corresponding to $C_{i}$ actually lies on the path from $A_{i}$ to $B_{i}$ . Let $L$ be the least common ancestor of $A_{i}$ and $B_{i} .$ First, we can check whether $y$ is an ancestor of $B_{i}$ in $O (1)$ using the preorder and postorder traversals of the tree. If not, then $y$ lies on the path between $A_{i}$ and $L_{i},$ so the answer to this query must be 1. If yes, then it's still possible for $y$ to lie on the path from $A_{i}$ to $B_{i}$ if $y = L_{i}$ .

One option is to actually find $L_{i}$ and compare it to $y,$ but this is unnecessary. Instead, if $y \neq A_{i}$ then consider the farm $Y = o r d [d e p t h [y] + 1] .$ If $Y$ is an ancestor of $B_{i},$ then $y$ is clearly not the LCA. Otherwise, $A_{i}$ and $B_{i}$ lie in different child subtrees of $y,$ implying that $y$ is the LCA.

Thus, this problem is solvable in $O (N + M)$ time.

#include <bits/stdc++.h>
using namespace std;
 
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;
 
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= (a); i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define trav(a, x) for (auto& a : x)
 
#define mp make_pair
#define pb push_back
#define f first
#define s second
 
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rsz resize
 
const int MX = 100005;

void setIO(string name) {
    ios_base::sync_with_stdio(0); cin.tie(0);
    freopen((name+".in").c_str(),"r",stdin);
    freopen((name+".out").c_str(),"w",stdout);
}

int N,M,T[MX],C[MX];
bool ok[MX];
vi adj[MX];
array<int,2> dat[MX];
vi todo[MX];
pi range[MX];
 
int co = 0;
void dfs(int x, int y) {
	range[x].f = co++;
	trav(t,adj[x]) if (t != y) dfs(t,x);
	range[x].s = co-1;
}
 
vpi stor[MX];
vi ord;
 
bool anc(int a, int b) {
	return range[a].f <= range[b].f && range[b].s <= range[a].s;
}
 
void dfs2(int x, int y) {
	stor[T[x]].pb({x,sz(ord)}); ord.pb(x);
	trav(t,todo[x]) if (sz(stor[C[t]])) {
		pi y = stor[C[t]].back();
		if (y.f == x) ok[t] = 1;
		else {
			int Y = ord[y.s+1];
			// x is one of endpoints for query t
			assert(dat[t][0] == x || dat[t][1] == x); 
			if (!anc(Y,dat[t][0]+dat[t][1]-x)) ok[t] = 1;
		}
	}
	trav(t,adj[x]) if (t != y) dfs2(t,x);
	stor[T[x]].pop_back(); ord.pop_back();
}
 
int main() {
	setIO("milkvisits"); 
	cin >> N >> M;
	FOR(i,1,N+1) cin >> T[i];
	F0R(i,N-1) {
		int A,B; cin >> A >> B;
		adj[A].pb(B), adj[B].pb(A);
	}
	dfs(1,0);
	F0R(i,M) {
		cin >> dat[i][0] >> dat[i][1] >> C[i];
		F0R(j,2) todo[dat[i][j]].pb(i);
	}
	dfs2(1,0);
	F0R(i,M) {
		if (ok[i]) cout << 1;
		else cout << 0;
	}
	cout << "\n";
}

Bonus: solve the problem online in $O ((N + M) \log N) .$

[/hide]