First Solve: arvindf232
What happens when adding an edge between two nodes with distance of $$$k$$$ (amount of edges in the simple path from one node to another is $$$k$$$)?
Suppose that the amount of edges in the simple path from $$$u$$$ to $$$v$$$ is $$$k$$$. Adding a new edge $$$(u, v)$$$ will create a new cycle of $$$k$$$ nodes (with $$$k+1$$$ edges). Therefore, in order to create a cycle of size at least $$$3$$$, it is enough to find any two nodes that are not adjacent and connect them.
Due to the small constraints, it is enough to try all possible pairs of nodes and check if they're neighbors or not.
#include <bits/stdc++.h>
using namespace std;
vector<set<int>> tree;
void solve() {
int n; cin >> n;
tree.resize(n+1);
for (int i = 1; i < n; i++) {
int u, v; cin >> u >> v;
tree[u].insert(v);
tree[v].insert(u);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) continue;
if (tree[i].find(j) == tree[i].end()) {
cout << i << " " << j << "\n";
return;
}
}
}
}
int main() {
solve();
return 0;
}
#include<bits/stdc++.h>
#define pi 3.14159265358979323846
#define eb emplace_back
#define ll long long
#define w(t) while(t--)
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std;
//give sin(),cos() radian, and asin(),acos() gives you radian
bool ch[110][110];
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int n,a,b;
cin>>n;
for(int i=1;i<n;i++){
cin>>a>>b;
ch[a][b]=1;
ch[b][a]=1;
}
for(int i=1;i<n;i++){
for(int j=i+1;j<=n;j++){
if(!ch[i][j]){
cout<<i<<' '<<j;
return 0;
}
}
}
return 0;
}
Can you solve this problem in $$$O(n)$$$ and without any tree traversal algorithms?
Problem B — Tree Game (Idea by rangerscowboys)
First Solve: arvindf232
If $$$d$$$ is the root of the tree, what is Spyrosaliv's best strategy? What is Cow the Cow's?
Spyrosaliv has a greedy strategy.
Spyrosaliv will keep decreasing the depth of the node he is on, until he reaches the root. How can Cow the Cow prevent this?
Spyrosaliv plays first, therefore if $$$s$$$ is adjacent to $$$d$$$ he wins.
Otherwise, it is impossible for him to win.
Let's root the tree at node $$$d$$$. Now, Spyrosaliv's goal is to reach the root node with depth $$$1$$$. Spyrosaliv has a greedy strategy: to keep decreasing the depth of his position, until he wins.
In his first move, he will decrease his position's depth by climbing upwards. However, whenever Cow the Cow plays, he can do the following: block the edge $$$(u, p_u)$$$, where $$$u$$$ is Spyrosaliv's current node and $$$p_u$$$ the parent of node $$$u$$$. Since Spyrosaliv has to move, his node's depth will keep increasing with each move until he reaches a leaf node and loses.
#include <bits/stdc++.h>
using namespace std;
const int MN = 2e5+1;
vector<vector<int>> tree(MN);
void solve() {
int n, s, d; cin >> n >> s >> d;
for (int i = 1; i < n; i++) {
int u, v; cin >> u >> v;
tree[u].push_back(v);
tree[v].push_back(u);
}
for (auto next: tree[s]) {
if (next == d) {
cout << "YES\n";
return;
}
}
cout << "NO\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
Suppose there are $$$q$$$ queries. In each query, you are asked about the answer for different values of $$$s$$$ and $$$d$$$. How can you solve this problem in $$$O(n + q)$$$?
First Solve: arvindf232
What is a property of a node $$$u$$$ that makes it impossible to win starting from that node?
Notice that it is always possible to win starting from the root of any tree. Why so?
Think of the way a DFS traversal visits the nodes of a tree.
For each node, if it is the root or its parent has more than $$$1$$$ child, then you can win starting from that node. Otherwise, you cannot.
Suppose we start from node $$$u \neq 1$$$ such that $$$cnt_{p_u} = 1$$$, where $$$p_u$$$ is the parent of node $$$u$$$ and $$$cnt_u$$$ is the number of children of node $$$u$$$. We know that no matter which way we move, node $$$u$$$ will be painted first. Therefore, $$$p_u$$$ will be an unpainted node that is not a leaf with all of its children painted, therefore we lose.
Now, let's see how to always paint a tree if we start from its root. The optimal strategy is to paint nodes in the dfs traversal. That's because the dfs traversal in a tree starting from its root visits all nodes without having to visit any node twice, and it only goes upwards whenever visiting a leaf node.
To paint a tree starting from a node $$$u \neq 1$$$ with $$$cnt_{p_u} > 1$$$, we will first paint the subtree rooted at $$$u$$$. Then, we will move to node $$$1$$$ and paint the rest of the tree.
#include <bits/stdc++.h>
using namespace std;
const int MN = 2e5+1;
void solve() {
int n; cin >> n;
vector<int> cnt(n+1, 0), par(n+1);
for (int i = 2; i <= n; i++) {
int p; cin >> p;
cnt[p]++;
par[i] = p;
}
cout << 1;
for (int i = 2; i <= n; i++) {
cout << (cnt[par[i]] >= 2);
}
cout << "\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
Suppose that the $$$i$$$-$$$th$$$ node has been assigned with a value $$$c_i$$$. You need $$$1$$$ second to paint a node. Painting node $$$u$$$ at the $$$j$$$-$$$th$$$ second costs $$$j \cdot c_u$$$ coins. What is the minimum amount of coins needed to paint the whole tree (if possible to paint it)?
First Solve: arvindf232
We don't care about which edge has been assigned to what weight.
We can try creating the best path on the diameter of the tree.
We can swap any two weights as many times as we'd like, so we don't care about which edge has been assigned to what weight.
Let $$$pos$$$ denote the array of positive weights and $$$neg$$$ the array of negative weights, both sorted in descending order. Also let $$$p$$$ and $$$n$$$ denote the size of $$$pos$$$ and $$$neg$$$ respectively.
Notice that the optimal strategy is to first pick the edge with the maximum weight, then the edge with the maximum negative weight, then the edge with the second maximum weight, and so on. More formally, let $$$s_i$$$ be the best path of $$$i$$$ edges, for all $$$1 \le i \le 2*\min(p, n)$$$. Then, $$$s_i = \sum_{j=1}^{j= \lceil{\frac{i}{2}}\rceil} pos_j + \sum_{j=1}^{j= \lfloor{\frac{i}{2}}\rfloor} neg_j$$$.
Notice that there is one last restriciton: since we are placing the weights on edges of the tree, we cannot make a best path that needs more edges than the diameter of the tree.
Let $$$d$$$ be the amount of edges in the diameter of the tree. The answer will be $$$\max\limits_{1 \le i \le \min(d, 2*p)} s_i$$$.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MN = 2e5+1;
vector<vector<int>> tree(MN);
int n;
int diameter = 0, firstEnd = 0;
void dfs(int node, int par = 0, int d = 0) {
if (d > diameter) {
diameter = d;
firstEnd = node;
}
for (auto next: tree[node]) {
if (next != par) dfs(next, node, d+1);
}
}
void find_diameter() {
dfs(1);
dfs(firstEnd);
}
void solve() {
cin >> n;
vector<int> pos, neg;
for (int i = 1; i < n; i++) {
int u, v, w; cin >> u >> v >> w;
tree[u].push_back(v);
tree[v].push_back(u);
if (w > 0) pos.push_back(w);
else neg.push_back(w);
}
sort(pos.rbegin(), pos.rend());
sort(neg.rbegin(), neg.rend());
if (pos.size() == 0) {
cout << neg[0] << "\n";
return;
}
vector<ll> fin;
int pSz = pos.size(), nSz = neg.size();
for (int i = 0; i < n; i++) {
if (i % 2 == 0) {
if (i / 2 == pSz) {
fin.pop_back();
break;
}
else fin.push_back(pos[i/2]);
}
else {
if (i / 2 == nSz) break;
else fin.push_back(neg[i/2]);
}
}
int sz = fin.size();
for (int i = 1; i < sz; i++) fin[i] += fin[i-1];
find_diameter();
ll ans = 0;
for (int i = 0; i < min(sz, diameter); i++) {
ans = max(ans, (ll)fin[i]);
}
cout << ans << "\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
What if you could perform at most $$$k$$$ operations?
First Solve: arvindf232
Two nodes $$$a$$$ and $$$b$$$ are considered similiar if and only if there exists another node $$$c$$$ such that it is an ancestor of both $$$a$$$ and $$$b$$$ and $$$dist(a, c) \equiv dist(b, c) \equiv 0 \pmod{k}$$$. Then, $$$c$$$ is going to be similiar to $$$a$$$, as $$$dist(a, c) \equiv dist(c, c) \equiv 0 \pmod{k}$$$, since $$$c$$$ is an ancestor of itself. For the same reason, $$$b$$$ is similiar to $$$c$$$. Furthermore, a node is similiar to all of its descendants with distance divisible by $$$k$$$, so all those nodes are similiar to each other.
For those reasons, the similarity is transmissive: if a node $$$u$$$ is similiar to a node $$$v$$$, and node $$$v$$$ is similiar to a node $$$x$$$, then node $$$u$$$ is similiar to node $$$x$$$. Therefore, all similiar nodes form non-intersecting components.
This observation leads us to think of the problem from a different prespective. Instead of going over all possible pairs $$$a$$$ and $$$b$$$, we can iterate over all possible nodes as $$$c$$$ (the ancestor of $$$a$$$ and $$$b$$$). Then, we are going to place all descendants with distance exactly $$$k$$$ inside the same component as node $$$c$$$.
The final part of the solution can be done in two ways, as listed below.
This solution uses DP on tree.
Let $$$dp_u$$$ be the number of nodes under $$$u$$$'s subtree with distance from $$$u$$$ divisible by $$$k$$$. If we do a dfs starting from the leaves, and the $$$k$$$-$$$th$$$ ancestor of a node $$$v$$$ is $$$u$$$, the transition will be $$$dp_u := dp_v + dp_u$$$. Initially $$$dp_u = 1$$$ for all $$$n$$$ nodes (since the distance of a node from itself is $$$0$$$, which is divisible by $$$k$$$).
The answer will be the sum of $$$\frac{dp_u \cdot (dp_u - 1)}{2}$$$ for all nodes $$$u$$$ with depth up to $$$k$$$.
This solution uses Disjoint Set Union (DSU).
Let the $$$k$$$-$$$th$$$ ancestor of a node $$$u$$$ be $$$a_u$$$. Then, we will use DSU to merge nodes $$$u$$$ and $$$a_u$$$ for every node with depth of at least $$$k + 1$$$. Let the sizes of the final components be $$$s_1, s_2, ..., s_l$$$, where $$$l$$$ is the amount of the final components.
The answer will be $$$\sum_{i = 1}^{i = l} \frac{s_i \cdot (s_i - 1)}{2}$$$.
We do not need to use binary lifting or anything advanced to get the $$$k$$$-$$$th$$$ ancestor of each node.
A quicker approach can be implemented instead.
In the DFS, let your current position be $$$u$$$. If depth of $$$u$$$ is $$$k + 1$$$, then its $$$k$$$-$$$th$$$ ancestor is node $$$1$$$. Otherwise, if the depth is greater than $$$k + 1$$$, its $$$k$$$-$$$th$$$ ancestor is the most recently visited child of the $$$k$$$-$$$th$$$ ancestor of the parent of node $$$u$$$. Check implementations for more details.
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MN = 2e5+1;
vector<vector<int>> tree(MN);
vector<int> up(MN); // store k-th ancestor for all nodes
vector<int> mainChild(MN), dp(MN, 1);
int n, k, ans = 0;
void dfs1(int node, int par, int dis) { // fill up array
if (dis == k) {
up[node] = 1;
}
else if (dis > k) {
up[node] = mainChild[up[par]];
}
else up[node] = -1;
for (auto next: tree[node]) {
if (next != par) {
mainChild[node] = next;
dfs1(next, node, dis+1);
}
}
if (up[node] != -1) dp[up[node]] += dp[node];
if (dis < k) ans += dp[node]*(dp[node] - 1)/2;
}
void solve() {
cin >> n >> k;
for (int i = 2; i <= n; i++) {
int p; cin >> p;
tree[p].push_back(i);
}
dfs1(1, 0, 0);
cout << ans << "\n";
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
//freopen("file.in", "r", stdin)
//freopen("file.out", "w", stdout);
int t = 1;
while (t--) solve();
return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MN = 2e5+1;
vector<vector<int>> tree(MN);
vector<int> up(MN); // store k-th ancestor for all nodes
vector<int> mainChild(MN);
int n, k, ans = 0;
int par[MN], sz[MN];
int find(int a) {
if (a == par[a]) return a;
return par[a] = find(par[a]);
}
void merge(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return;
if(sz[a] > sz[b]) swap(a, b);
par[a] = b;
sz[b] += sz[a];
}
void dfs1(int node, int par, int dis) { // fill up array
if (dis == k) {
up[node] = 1;
}
else if (dis > k) {
up[node] = mainChild[up[par]];
}
else up[node] = -1;
for (auto next: tree[node]) {
if (next != par) {
mainChild[node] = next;
dfs1(next, node, dis+1);
}
}
if (up[node] != -1) {
merge(node, up[node]);
}
}
void solve() {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
par[i] = i;
sz[i] = 1;
}
for (int i = 2; i <= n; i++) {
int p; cin >> p;
tree[p].push_back(i);
}
dfs1(1, 0, 0);
vector<bool> added(n+1, false);
for (int i = 1; i <= n; i++) {
int rep = find(i);
if (!added[rep]) {
added[rep] = true;
ans += sz[rep] * (sz[rep] - 1) / 2;
}
}
cout << ans << "\n";
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
//freopen("file.in", "r", stdin)
//freopen("file.out", "w", stdout);
int t = 1;
while (t--) solve();
return 0;
}
First Solve: Chaeryeong
We need to count the number of unordered pairs of nodes $$$(u, v)$$$ such that $$$(d_v + d_u)^2 = (d_v - d_u)^2 = dis(u, v)$$$ holds.
Solving the first equality:
Therefore, $$$d_u = 0$$$ or $$$d_v = 0$$$ should hold.
WLOG, assume $$$d_v = 0$$$. Then, solving the second equality:
Let $$$D = 1 - 8d_{lca(u, v)} + 4val_{lca(u, v)}$$$. By the Quadratic Formula, $$$d_u = \frac{1 \pm \sqrt{D}}{2}$$$, if $$$D > 0$$$ and $$$D$$$ an odd perfect square.
This allows us to count the number of pairs under a node's subtree if we treat that node as $$$lca(u, v)$$$. The actual counting can be done with Small-To-Large Merging, by keeping a frequency map for each node.
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MN = 2e5+5;
const int MAXV = 1e8;
vector<vector<int>> tree(MN);
vector<int> val(MN), match(MN, 0);
vector<map<int, int>> subVals(MN);
int ans = 0, n;
void dfs(int node, int d = 0) {
d += val[node];
subVals[node][d]++;
int D = 1 - 8 * d + 4 * val[node];
int sol1 = 1e8+5, sol2 = 1e8+5;
if (D % 2 == 1) {
int s = sqrt(D);
if (s * s == D) {
sol1 = (1 + s)/2;
sol2 = (1 - s)/2;
}
}
for (auto next: tree[node]) {
dfs(next, d);
if (subVals[next].size() < subVals[node].size()) swap(subVals[next], subVals[node]);
for (auto [a, b]: subVals[next]) {
if (a == sol1 || a == sol2) {
ans += b * subVals[node][0];
}
else if (a == 0) {
ans += b * subVals[node][sol1];
ans += b * subVals[node][sol2];
}
}
for (auto [a, b]: subVals[next]) {
if (abs(a) > MAXV) continue;
subVals[node][a] += b;
}
}
}
void solve() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> val[i];
for (int i = 2; i <= n; i++) {
int p; cin >> p;
tree[p].push_back(i);
}
dfs(1);
cout << ans << "\n";
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <bitset>
#include <unordered_map>
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll TMD=0;
const ll INF=2147483647;
int T,n;
ll ans;
ll val[N],fa[N],d[N],numS[N];
vector<int> G[N];
set<pair<ll,ll> > S[N];
/*
* stuff you should look for
* [Before Submission]
* array bounds, initialization, int overflow, special cases (like n=1), typo
* [Still WA]
* check typo carefully
* casework mistake
* special bug
* stress test
*/
void init()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>val[i];
for(int i=2;i<=n;i++)
{
cin>>fa[i];
G[i].push_back(fa[i]);
G[fa[i]].push_back(i);
}
}
void uni_set(int x,int y)
{
if(x==y) return ;
while(!S[y].empty())
{
pair<ll,ll> pr=*S[y].begin();
set<pair<ll,ll> >::iterator it=S[x].lower_bound(make_pair(pr.first,0));
S[y].erase(pr);
if(it==S[x].end()||it->first!=pr.first) S[x].insert(pr);
else
{
pr.second+=it->second;
S[x].erase(it);
S[x].insert(pr);
}
}
}
ll count_occ(ll x,ll v)
{
set<pair<ll,ll> >::iterator it=S[x].lower_bound(make_pair(v,0));
if(it==S[x].end()||it->first!=v) return 0;
else return it->second;
}
pair<ll,ll> solve_equation(ll C)
{
//solve x^2-x-C=0
ll delta=1+4*C,sd;
if(delta<0) return make_pair(INF*INF,INF*INF);
sd=(ll)sqrt(delta);
if(sd*sd!=delta||(sd%2==0)) return make_pair(INF*INF,INF*INF);
else return make_pair((1+sd)/2,(1-sd)/2);
}
void DFS(int x)
{
//
//printf("x=%d\n",x);
//
ll mxsz=0,mxnum;
d[x]=val[x]+d[fa[x]];
for(int i=0;i<G[x].size();i++)
{
int y=G[x][i];
if(y==fa[x]) continue;
DFS(y);
if(S[numS[y]].size()>mxsz)
mxsz=S[numS[y]].size(),mxnum=numS[y];
}
if(x!=1&&G[x].size()==1)
{
numS[x]=x;
S[x].insert(make_pair(d[x],1));
return ;
}
ll C=val[x]-2*d[x];
pair<ll,ll> root=solve_equation(C);
if(root.first!=INF*INF)
{
ll r[2]={root.first,root.second};
ll c0=(d[x]==0);
for(int i=0;i<G[x].size();i++)
{
int y=G[x][i];
if(y==fa[x]) continue;
c0+=count_occ(numS[y],0);
}
for(int i=0;i<2;i++)
{
ll tans=0;
for(int j=0;j<G[x].size();j++)
{
int y=G[x][j];
if(y==fa[x]) continue;
tans+=count_occ(numS[y],r[i])*(c0-count_occ(numS[y],0));
}
if(d[x]==r[i])
tans+=(c0-(d[x]==0));
if(!r[i]) tans/=2;
ans+=tans;
}
}
numS[x]=mxnum;
for(int i=0;i<G[x].size();i++)
{
int y=G[x][i];
if(y==fa[x]) continue;
if(numS[y]!=mxnum) uni_set(mxnum,numS[y]);
}
S[x].insert(make_pair(d[x],1));
uni_set(mxnum,x);
}
void solve()
{
DFS(1);
cout<<ans<<'\n';
}
//-------------------------------------------------------
void gen_data()
{
srand(time(NULL));
}
int bruteforce()
{
return 0;
}
//-------------------------------------------------------
int main()
{
fastio;
T=1;
//cin>>T;
while(T--)
{
init();
solve();
/*
//Stress Test
gen_data();
auto ans1=solve(),ans2=bruteforce();
if(ans1==ans2) printf("OK!\n");
else
{
//Output Data
}
*/
}
return 0;
}
First Solve: arvindf232
Before solving the actual problem, let's see an easier version where no nodes are ever blocked.
First, let's see what is the optimal strategy for the cows. Since every cow has a positive value and their priority is to maximize the score of the game, they will all meet at the same node. In order to minimize the time of the game, they will meet at the node that is the closest to every cow and that is an ancestor of all nodes with a cow.
Let the current game be represented by an integer $$$k$$$ — the number of cows, and $$$pos_1, pos_2, ..., pos_k$$$, where $$$pos_i$$$ is the node of the $$$i$$$-$$$th$$$ cow. Then, the node they will meet at is $$$u = lca(pos_1, pos_2, ..., pos_k)$$$. Let $$$dep_u$$$ be the depth of node $$$u$$$. Then it's easy to see that the time they will need to meet at that $$$u$$$ is going to be $$$\max\limits_{1 \le i \le k} (dep_{pos_i}) - dep_u$$$.
Now, we just need to efficiently calculate these values for each game. Notice that $$$lca(x, y, z) = lca(x, lca(y, z))$$$. Therefore, we can reverse the queries and answer them offline. Now, each query pretty much is asking to add a cow instead of removing one. That's easier to keep track of, since we can keep the sum of the values of the cows, the deepest node a cow is on, and their LCA for each query.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MN = 2e5+5;
vector<vector<int>> tree(MN), up;
vector<int> val(MN), pos(MN), depth(MN, 0), par(MN), sz(MN);
vector<ll> tin(MN), tout(MN);
int n, k, t = 0, l;
ll ans = 0;
bool is_anc(int u, int v) {
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int a, int b) {
if (a == b) return a;
if (depth[a] < depth[b]) swap(a, b);
int curr = a;
for (int i = l; i >= 0; i--) {
if (!is_anc(up[curr][i], b)) curr = up[curr][i];
}
return up[curr][0];
}
void dfs1(int node, int p = 0, int d = 1) {
depth[node] = d;
tin[node] = t;
t++;
up[node][0] = p;
for (int i = 1; i <= l; i++) {
up[node][i] = up[up[node][i-1]][i-1];
}
for (auto next: tree[node]) {
if (next != p) dfs1(next, node, d+1);
}
tout[node] = t;
t++;
}
void solve() {
cin >> n >> k;
l = ceil(log2(n));
up.assign(n+1, vector<int>(l+1, 0));
tin[0] = 0;
tout[0] = LLONG_MAX;
ll ans = 0;
vector<bool> hasCow(n+1, false);
for (int i = 1; i <= k; i++) {
cin >> pos[i];
hasCow[pos[i]] = true;
}
for (int i = 1; i <= k; i++) {
cin >> val[pos[i]];
ans += val[pos[i]];
}
for (int i = 2; i <= n; i++) {
int p; cin >> p;
tree[p].push_back(i);
tree[i].push_back(p);
}
int q; cin >> q;
vector<pair<int, int>> queries(q);
for (auto &[t, u]: queries) {
cin >> t >> u;
ans -= val[u];
hasCow[u] = false;
}
dfs1(1);
int lc = 0, deepest = 0;
for (int i = 1; i <= n; i++) {
if (hasCow[i]) {
deepest = max(deepest, depth[i]);
if (lc == 0) lc = i;
else lc = lca(lc, i);
}
}
vector<pair<ll, int>> answers;
answers.push_back({ans, deepest - depth[lc]});
reverse(queries.begin(), queries.end());
for (auto [t, u]: queries) {
ans += val[u];
if (lc == 0) lc = u;
else lc = lca(lc, u);
deepest = max(deepest, depth[u]);
answers.push_back({ans, deepest - depth[lc]});
}
reverse(answers.begin(), answers.end());
for (auto [a, b]: answers) cout << a << " " << b << "\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
Now we can solve the actual problem.
Notice that blocking a node splits the tree into multiple components. More specifically, by blocking a node, we split the whole game into multiple smaller games. Out of all the non-intersecting & smaller games, we will keep the one with the maximum final score. If there are many such games, we will keep the one with the minimum time needed to be finished. These two values will be the answer to each query.
But how do we handle multiple games for many queries efficiently? Let's use the idea of the Easy Version of this problem. That is, we will reverse the queries, as adding cows and "unblocking" nodes is easier to do than removing cows and blocking nodes. As mentioned before, we have multiple components, each representing a different game. For each such component, we need to maintain the same information as for the Easy Version: the deepest node with a cow, the LCA of all nodes with a cow and the total sum of the values of the cows.
To easily keep track of all components, we will use Disjoint Set-Union.
Merging two components is simple: the LCA of the new component will be the LCA of the LCAs of the two other components, the deepest node with a cow will be the deepest node with a cow from the two other components, and the total sum of values will be the sum of the values of the two components to be merged. In an identical way, we can add a cow to the tree.
To "unblock" a node, we will create a new component that initially consists only of this node. Then, we will iterate over all nodes that are not blocked and that are adjacent to this node and merge their components. Note that this is possible without going over the time limit, as each node can be "unblocked" at most once.
Finally, we will maintain the maximal possible score and the minimum time to achieve it and update these values accordingly for each new merge.
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MN = 2e5+5;
vector<vector<int>> tree(MN), up;
vector<int> val(MN), pos(MN), depth(MN, 0), par(MN), sz(MN), compLCA(MN), score(MN), deepest(MN), tin(MN), tout(MN);
vector<bool> blocked(MN, false), hasCow(MN, false);
int n, k, ans = 0, minTime = 0, t = 0, l;
bool is_anc(int u, int v) {
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int a, int b) {
if (a == b) return a;
if (depth[a] < depth[b]) swap(a, b);
int curr = a;
for (int i = l; i >= 0; i--) {
if (!is_anc(up[curr][i], b)) curr = up[curr][i];
}
return up[curr][0];
}
int find(int node) {
if (par[node] == node) return node;
return par[node] = find(par[node]);
}
void merge(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return;
if (sz[a] > sz[b]) swap(a, b);
par[a] = b;
sz[b] += sz[a];
if (hasCow[a] && hasCow[b]) {
int x = lca(compLCA[b], compLCA[a]);
compLCA[b] = x;
}
else if (hasCow[a]) {
compLCA[b] = compLCA[a];
hasCow[b] = true;
}
score[b] = score[b] + score[a];
deepest[b] = max(deepest[b], deepest[a]);
if (score[b] == ans) {
minTime = min(minTime, abs(depth[compLCA[b]] - deepest[b]));
}
else if (score[b] > ans) {
ans = score[b];
minTime = abs(depth[compLCA[b]] - deepest[b]);
}
}
void dfs1(int node, int p = 0, int d = 1) {
depth[node] = d;
if (hasCow[node]) deepest[node] = d;
if (hasCow[node]) compLCA[node] = node;
tin[node] = t;
t++;
up[node][0] = p;
for (int i = 1; i <= l; i++) {
up[node][i] = up[up[node][i-1]][i-1];
}
for (auto next: tree[node]) {
if (next != p) dfs1(next, node, d+1);
}
tout[node] = t;
t++;
}
void dfs2(int node, int p = 0) {
for (auto next: tree[node]) {
if (next != p) {
dfs2(next, node);
if (!blocked[node] && !blocked[next]) merge(node, next);
}
}
}
void solve() {
cin >> n >> k;
l = ceil(log2(n));
up.assign(n+1, vector<int>(l+1, 0));
tin[0] = 0;
tout[0] = LLONG_MAX;
for (int i = 1; i <= n; i++) {
par[i] = i;
sz[i] = 1;
compLCA[i] = i;
score[i] = 0;
deepest[i] = 0;
}
for (int i = 1; i <= k; i++) {
cin >> pos[i];
hasCow[pos[i]] = true;
}
for (int i = 1; i <= k; i++) {
cin >> val[pos[i]];
score[pos[i]] = val[pos[i]];
}
for (int i = 2; i <= n; i++) {
int p; cin >> p;
tree[p].push_back(i);
tree[i].push_back(p);
}
int q; cin >> q;
vector<pair<int, int>> queries(q);
for (auto &[t, u]: queries) {
cin >> t >> u;
if (t == 1) {
hasCow[u] = false;
score[u] = 0;
}
else blocked[u] = true;
}
dfs1(1);
dfs2(1);
for (int i = 1; i <= n; i++) ans = max(ans, score[i]);
if (q == 0) {
cout << ans << " " << minTime << "\n";
return;
}
vector<pair<int, int>> answers;
answers.push_back({ans, minTime});
reverse(queries.begin(), queries.end());
for (auto [t, u]: queries) {
if (t == 2) { // unblock u
blocked[u] = false;
for (auto x: tree[u]) {
if (!blocked[x]) merge(x, u);
}
}
else {
int rep = find(u);
int plusScore = val[u];
if (!hasCow[rep]) {
hasCow[rep] = true;
score[rep] = plusScore;
deepest[rep] = depth[u];
compLCA[rep] = u;
}
else {
score[rep] += plusScore;
deepest[rep] = max(deepest[rep], depth[u]);
compLCA[rep] = lca(compLCA[rep], u);
}
if (score[rep] == ans) {
minTime = min(minTime, abs(depth[compLCA[rep]] - deepest[rep]));
}
if (score[rep] > ans) {
ans = score[rep];
minTime = abs(depth[compLCA[rep]] - deepest[rep]);
}
}
answers.push_back({ans, minTime});
}
reverse(answers.begin(), answers.end());
for (auto [a, b]: answers) cout << a << " " << b << "\n";
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
//freopen("file.in", "r", stdin)
//freopen("file.out", "w", stdout);
int t = 1;
while (t--) solve();
return 0;
}
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <bitset>
#include <unordered_map>
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int N=200010;
const int LOGN=28;
const ll TMD=0;
const ll INF=2147483647;
int T,n,k,q;
ll pos[N],val[N],cow[N],t[N],u[N];
/*
* stuff you should look for
* [Before Submission]
* array bounds, initialization, int overflow, special cases (like n=1), typo
* [Still WA]
* check typo carefully
* casework mistake
* special bug
* stress test
*/
struct state
{
ll num,sum,tm;
state() {}
state(ll num,ll sum,ll tm):num(num),sum(sum),tm(tm) {}
friend bool operator <(state x,state y)
{
if(x.sum!=y.sum) return x.sum>y.sum;
else if(x.tm!=y.tm) return x.tm<y.tm;
else return x.num<y.num;
}
};
set<state> S;
//-------------------------------------------------
//涉及变量:n(点数),G(图),d[](节点深度),f[][](祖先ST表)
//注意: 节点编号为1-n
ll rt=1;
ll d[N];
ll f[N][LOGN];
vector<int> G[N];
void DFS(int x,int pre)
{
f[x][0]=pre;
d[x]=d[pre]+1;
for(int i=0;i<G[x].size();i++)
{
int y=G[x][i];
if(y==pre) continue;
DFS(y,x);
}
}
void init_lca() //算出d[],f[][]
{
DFS(rt,0);
for(int i=1;i<LOGN;i++)
for(int j=1;j<=n;j++)
f[j][i]=f[f[j][i-1]][i-1];
}
int lca(int x,int y)
{
//
if(x==0) return y;
if(y==0) return x;
//
if(d[x]>d[y]) swap(x,y);
for(int i=LOGN-1;i>=0;i--) if(d[f[y][i]]>=d[x]) y=f[y][i];
if(x==y) return x;
for(int i=LOGN-1;i>=0;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
return f[x][0];
}
//-------------------------------------------------
//-------------------------------------------------
//涉及变量:f[]
//注意:自行初始化
ll F[N],LCA[N],mxd[N],sum[N];
int find(int x)
{
return x==F[x]?x:F[x]=find(F[x]);
}
void uni(int x,int y)
{
int fx=find(x),fy=find(y);
F[fx]=fy;
if(fx==fy) return;
S.erase(state(fx,sum[fx],mxd[fx]-d[LCA[fx]]));
S.erase(state(fy,sum[fy],mxd[fy]-d[LCA[fy]]));
LCA[fy]=lca(LCA[fx],LCA[fy]);
mxd[fy]=max(mxd[fx],mxd[fy]);
sum[fy]+=sum[fx];
S.insert(state(fy,sum[fy],mxd[fy]-d[LCA[fy]]));
//if(fx!=fy) sz[fy]+=sz[fx]; //!!!
}
//-------------------------------------------------
void init()
{
cin>>n>>k;
for(int i=1;i<=k;i++) cin>>pos[i];
for(int i=1;i<=k;i++) cin>>val[i];
for(int i=2;i<=n;i++)
{
int fa;
cin>>fa;
G[i].push_back(fa);
G[fa].push_back(i);
}
cin>>q;
for(int i=1;i<=q;i++)
cin>>t[i]>>u[i];
for(int i=1;i<=k;i++) cow[pos[i]]=i;
init_lca();
for(int i=1;i<=n;i++) F[i]=i;
}
void solve()
{
vector<int> removed(n+4),blocked(n+4);
vector<state> ans;
for(int i=1;i<=q;i++)
if(t[i]==1) removed[u[i]]=1;
for(int i=1;i<=q;i++)
if(t[i]==2) blocked[u[i]]=1;
for(int i=1;i<=k;i++)
{
if(removed[pos[i]]) continue;
LCA[pos[i]]=pos[i];
mxd[pos[i]]=d[pos[i]];
sum[pos[i]]=val[i];
}
for(int i=1;i<=n;i++)
S.insert(state(i,sum[i],0));
/*
cout<<"n="<<n<<'\n';
cout<<"pos[3]="<<pos[3]<<'\n';
cout<<"val[3]="<<val[3]<<'\n';
cout<<"sum[5]="<<sum[5]<<'\n';
cout<<"init "<<S.begin()->sum<<' '<<S.begin()->tm<<'\n';
while(!S.empty())
{
cout<<"fk "<<S.begin()->sum<<' '<<S.begin()->tm<<'\n';
S.erase(S.begin());
}
*/
for(int i=1;i<=n;i++)
{
if(blocked[i]) continue;
for(int j=0;j<G[i].size();j++)
{
int y=G[i][j];
if(!blocked[y]) uni(i,y);
}
}
//cout<<S.begin()->sum<<' '<<S.begin()->tm<<'\n';
ans.push_back(*S.begin());
for(int i=q;i;i--)
{
if(t[i]==1)
{
int fx=find(u[i]);
S.erase(state(fx,sum[fx],mxd[fx]-d[LCA[fx]]));
LCA[fx]=lca(LCA[fx],u[i]);
mxd[fx]=max(mxd[fx],d[u[i]]);
sum[fx]+=val[cow[u[i]]];
S.insert(state(fx,sum[fx],mxd[fx]-d[LCA[fx]]));
}
else
{
blocked[u[i]]=0;
for(int j=0;j<G[u[i]].size();j++)
{
int y=G[u[i]][j];
if(!blocked[y]) uni(u[i],y);
}
}
//cout<<S.begin()->sum<<' '<<S.begin()->tm<<'\n';
ans.push_back(*S.begin());
}
reverse(ans.begin(),ans.end());
for(int i=0;i<q+1;i++)
cout<<ans[i].sum<<' '<<ans[i].tm<<'\n';
}
//-------------------------------------------------------
void gen_data()
{
srand(time(NULL));
}
int bruteforce()
{
return 0;
}
//-------------------------------------------------------
int main()
{
fastio;
T=1;
//cin>>T;
while(T--)
{
init();
solve();
/*
//Stress Test
gen_data();
auto ans1=solve(),ans2=bruteforce();
if(ans1==ans2) printf("OK!\n");
else
{
//Output Data
}
*/
}
return 0;
}
Originally, there was going to be a HLD Hard Version to this problem (which we ended up removing, as we were worried that there would be too much implementation for this contest), where there is a third type of query:
"3. Add cow with value $$$v$$$ to node $$$u$$$ (there is no cow at node $$$u$$$ beforehand)".
Thank you for my first contest @theforces , I could have solved D easily but I wasn't really good with my implementation. Loved , looking forward for more
amazing contest
As a tester, this is an orz editorial
Bruh, this problem idea that I came up with was a joke -_-