Home » 国际竞赛 » Details

USACO 2019 December Contest, Platinum Problem 2. Bessie's Snow Cow

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

USACO 2019 December Contest, Platinum Problem 2. Bessie's Snow Cow

Snow has arrived on the farm, and as she does at the beginning of every winter, Bessie is building a snow-cow! Most of the time, Bessie strives to make her sculpture look as much like a real cow as possible. However, feeling artistically inspired, this year she decides to pursue a more abstract route and build a sculpture in the shape of a tree, consisting of $N$ snowballs $(1 \leq N \leq 10^{5})$ connected by $N - 1$ branches, each connecting a pair of snowballs such that there is a unique path between every pair of snowballs.

Bessie has added a nose to one of the snowballs, so it represents the head of the abstract snow cow. She designates it as snowball number 1. To add more visual interest, she plans to dye some of the snowballs different colors in an artistic fashion by filling old milk pails with colored dye and splashing them onto the sculpture. Colors are identified by integers in the range $1 \dots 10^{5}$ , and Bessie has an unlimited supply of buckets filled with dyes of every possible color.

When Bessie splashes a snowball with a bucket of dye, all the snowballs in its subtree are also splashed with the same dye (snowball $y$ is in the subtree of snowball $x$ if $x$ lies on the path from $y$ to the head snowball). By splashing each color with great care, Bessie makes sure that all colors a snowball has been splashed with will remain visible. For example, if a snowball had colors $[1, 2, 3]$ and Bessie splashes it with color $4$ , the snowball will then have colors $[1, 2, 3, 4]$ .

After splashing the snowballs some number of times, Bessie may also want to know how colorful a part of her snow-cow is. The "colorfulness" of a snowball $x$ is equal to the number of distinct colors $c$ such that snowball $x$ is colored $c$ . If Bessie asks you about snowball $x$ , you should reply with the sum of the colorfulness values of all snowballs in the subtree of $x .$

Please help Bessie find the colorfulness of her snow-cow at certain points in time.

SCORING:

$Q$ is defined below.

Test cases 2-3 satisfy $N \leq 10^{2}, Q \leq 2 \cdot 10^{2} .$
Test cases 4-6 satisfy $N \leq 10^{3}, Q \leq 2 \cdot 10^{3} .$

INPUT FORMAT (file snowcow.in):

The first line contains $N,$ and the number of queries $Q$ ( $1 \leq Q \leq 10^{5}$ ).The next $N - 1$ lines each contain two space-separated integers $a$ and $b,$ describing a branch connecting snowballs $a$ and $b$ ( $1 \leq a, b \leq N$ ).

Finally, the last $Q$ lines each contain a query. A query of the form

1 x c

indicates that Bessie splashed a bucket of juice of color $c$ on snowball $x,$ coloring all snowballs in the subtree of $x$ . A line of the form

2 x

is a query for the sum of the colorfulness values of all snowballs in the subtree of $x$ . Of course, $1 \leq x \leq N$ and $1 \leq c \leq 10^{5} .$

OUTPUT FORMAT (file snowcow.out):

For each query of type 2, print the sum of colorfulness values within the corresponding subtree. Note that you should use 64-bit integers to avoid overflow.

SAMPLE INPUT:

SAMPLE OUTPUT:

After the first query of type 1, snowball 4 is dyed with color 1.

After the second query of type 1, snowballs 4 and 5 are dyed with color 1.

After the third query of type 1, all snowballs are dyed with color 1.

Problem credits: Michael Cao and Benjamin Qi

<h3>USACO 2019 December Contest, Platinum Problem 2. Bessie's Snow Cow 题解(翰林国际教育提供，仅供参考)</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 will use “node” interchangeably with “snowball.” Let’s start by representing the tree as an array. First, we can run a preorder traversal in $O (N)$ time. Let $s t [x]$ denote the index (starting from one) of node $x$ in the traversal and let $e n [x]$ denote the maximum index of any node in the subtree of $v$ . Then the subtree of $x$ corresponds exactly with all nodes with indices in the range $[s t [x], e n [x]] .$

For a fixed color $c,$ call a node ``special" if it is colored $c$ and its parent is not colored $c$ . For any node $x,$ let $s u b [x]$ denote the number of nodes in the subtree of $x .$ Then the number of nodes in its subtree that are colored $c$ is given by one of the following:

Case 1: If $x$ or one of its parents is special, then return $s u b [x]$ .
Case 2: Otherwise, return the sum of the subtree sizes of all special nodes in the subtree of $x .$

We can rewrite the answer for a query for the subtree of $x$ as the sum of two separate parts.

s u b [x] \cdot (# of special nodes above or equal to x) + \sum (subtree sizes of special nodes below x),

over special nodes of all colors. Whenever a previously uncolored node is colored, we add it to the set of special nodes for that color and possibly remove some of the nodes in that set.

Part 1: getting $(# of special nodes above or equal to x)$

Whenever we add a special node, use a binary indexed tree (BIT) to add 1 to all nodes in the range $[s t [x], e n [x]] .$ Then evaluating this quantity is equivalent to making a point query at $s t [x]$ .

Part 2: getting $\sum (subtree sizes of special nodes below x)$

Whenever we add a special node $y$ , use a BIT to add $s u b [y]$ to the index $s t [y] .$ Then we simply need to query the sum of all values in the BIT in the range $[s t [x] + 1, e n [x]] .$

Since we make $O (Q)$ updates to the sets and the two BIT's, our solution runs in $O (N + Q \log N) .$ My code follows.

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

typedef long long ll;
typedef vector<int> vi; 
 
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
 
#define pb push_back
#define ub upper_bound
#define s second
 
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);
}

const int MX = 100005;

template<class T, int SZ> struct BIT {
	T bit[SZ+1];
	void upd(int pos, T x) {
		for (; pos <= SZ; pos += (pos&-pos)) 
		bit[pos] += x;
	}
	T sum(int r) {
		T res = 0; for (; r; r -= (r&-r)) 
			res += bit[r];
		return res;
	}
	T query(int l, int r) { 
		return sum(r)-sum(l-1); 
	}	
};
 
BIT<ll,MX> A,B;
map<int,int> col[MX];
int st[MX], en[MX],sub[MX];
int N,Q;
vi adj[MX];
int co;
 
void dfs(int x, int y) {
	st[x] = ++co;
	trav(t,adj[x]) if (t != y) dfs(t,x);
	en[x] = co;
	sub[x] = en[x]-st[x]+1;
}
 
void upd(int x, int y) {
	A.upd(st[x],y); A.upd(en[x]+1,-y);
	B.upd(st[x],y*sub[x]);
}
 
int main() {
	setIO("snowcow");
	cin >> N >> Q;
	F0R(i,N-1) {
		int a,b; cin >> a >> b;
		adj[a].pb(b), adj[b].pb(a);
	}
	dfs(1,0);
	F0R(i,Q) {
		int t; cin >> t;
		if (t == 1) {
			int x,c; cin >> x >> c;
			auto it = col[c].ub(st[x]);
			if (it != begin(col[c]) && en[prev(it)->s] >= en[x]) continue;
			while (it != end(col[c]) && en[it->s] <= en[x]) {
				upd(it->s,-1);
				col[c].erase(it++);
			}
			col[c][st[x]] = x; upd(x,1);
		} else {
			int x; cin >> x;
			cout << sub[x]*A.sum(st[x])+B.query(st[x]+1,en[x]) << "\n";
		}
	}
}

[/hide]