Γραμμική λύση στο conflicts (35 Γ'φαση 3ο θέμα).

[doublemidi]

Βρήκα $Ο(n)$ λύση στο πρόβλημα που δεν χρειάζεται κανέναν περίπλοκο αλγόριθμο και ήθελα να το μοιραστώ, αφού την μέρα του διαγωνισμού συζητήθηκαν μονο λύσεις με $Ο(nlogn)$ και $O(nlog^2(n))$ χρόνο που ήθελαν small-to-large ή segment trees. Επειδή δεν υπάρχει λύση στο https://pdp-archive.github.io/ θα εξηγήσω την λύση μου από το μηδέν:

Αφού η ισχύς του $u$ είναι το άθροισμα των $f_w$ για κάθε $w$ στο υπόδεντρο του $u$, μπορούμε εύκολα να το υπολογίσουμε με dp on tree.
Θέτω $A_u$ την ισχύ του $u$.
Για κάθε node $u$, μας ζητάται να βρούμε το πλήθος nodes $w$ με $A_u == A_w$ έτσι ώστε να είναι το $u$ ούτε πρόγονος ούτε απόγονος του $w$.
Θέτω $ans_u$ το πλήθος αυτό.

1. Θέτω $all_u$ το πλήθος nodes $w$ με $A_u == A_w$.
2. Θέτω $up_u$ το πλήθος nodes $w$ με $Α_u == A_w$ με $w$ αυστηρός πρόγονος του $u$ (το $u$ δεν είναι αυστηρός πρόγονος του $u$).
3. Θέτω $down_u$ το πλήθος nodes $w$ με $A_u == A_w$ με $w$ στο υπόδεντρο του $u$ (το $u$ είναι στο υπόδεντρο του $u$).

Προφανώς $ans_u == all_u - up_u - down_u$.
Λύνουμε το $all_u$:
Λύνεται αρκετά εύκολα, με ένα frequency table (με std::unordered_map). Αυτό θέλει χρόνο $Ο(n)$.

Λύνουμε το $up_u$:
Με μία $dfs$, για κάθε node $u$ που θα επισκέπτεται η $dfs$ θα κρατάμε ένα frequency table που θα έχει τα nodes στο path απο το $u$ στο root. Έτσι υπολογίζεται το $up_u$. Αυτό θέλει χρόνο $O(n)$.

Λύνουμε το $down_u$:
Αυτό είναι το πιο δύσκολο κομμάτι. Κάνοντας ένα euler tour στο δέντρο (αποκαλούμε τον πίνακα ET, με start time του $u$, S_u, και end time Ε_u), ένα υπόδεντρο, γίνεται υποπίνακας. Το μέγεθος του πινακα ET είναι $\leq n$Έτσι, πρέπει να βρούμε το πλήθος nodes $w$στον υποπίνακα $[S_u, E_u)$ με $A_u == A_w$. Με την ιδέα του prefix count, αρκεί να βρούμε το πλήθος στο $[0, S_u)$ και στο $[0, Ε_u)$ και να τα αφαιρέσουμε. Για να απαντήσουμε αυτά τα prefix sum "queries" αυτά, θα χτίσουμε occurence table για κάθε διαφορετική τιμή του $A$ (πάλι με std::unordered_map). Το occurence table θα έχει για κάθε εμφάνιση τιμής, το index στο οποίο εμφανίζεται σε αύξουσα σειρά. Αυτό γίνεται σε $O(n)$ αν προσθέτουμε τις τιμές με την σειρά του euler tour.
Με μία binary search μπορούμε να απαντήσουμε κάθε query σε $O(logn)$, για τελική πολιπλοκότητα $O(nlogn)$. Πώς γίνεται να το ρίξουμε όμως σε γραμμικό;

Με την ιδέα της counting sort, μπορούμε να ταξινομίσουμε τα queries ως προς το $i$, όπου τα queries είναι της μορφής $[0, i]$ με $A_u == x$. Αυτό μπορούμε να το κάνουμε, αφού τα $i$ δεν ξεπερνάνε το $n$
Αφού τα queries έχουν πλέον μονοτονία, μπορούμε για κάθε occurence table να κρατάμε και ένα pointer που θα αντιστοιχεί στο τελευταίο index που είχε χρειαστεί σε προηγούμενο query (αρχίζει στην αρχή του table) και θα το προχωράμε δεξιά με γραμμική αναζήτηση μέχρι να φτάσει το σημείο που του ζητάται στο query. Αυτή η διαδικασία παίρνει $O(n)$ χρόνο, αφού σε κάθε σημείο
του occurence table μπαίνουμε το πολύ μία φορα, και βγαίνουμε το πολύ μία φορά.

Συνολικά ο αλγόριθμος παίρνει $Ο(n)$ χρόνο με την κρυμμένη σταθερά του std::unordered_map.

Είμαι ανοιχτός σε οποιαδήποτε απορία για την λύση, αλλα και ιδέες και λύσεις για το πρόβλημα!

Ο κώδικας (περνάει όλα τα testcases στον https://pdp-archive.github.io/ ):

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

typedef long long ll;
typedef long double ld;
#define vc vector
typedef vc<ll> vcll;
typedef vc<bool> vcb;
#define pr pair
typedef pr<ll, ll> prll;
typedef map<ll,ll> mapll;
#define umap unordered_map
typedef umap<ll,ll> umapll;

#define f0r(i,a,n) for ((i)=(a); (i)<=(n); (i)++)
#define r0f(i,n,a) for ((i)=(n); (i)>=(a); (i)--)

#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define mp make_pair
#define fi first
#define se second
#define sz size
#define all(x) (x).begin(), (x).end()
#define all0(x, n) (x).begin(), (x).begin()+n
#define all1(x, n) (x).begin()+1, (x).begin()+n+1
#define allrev(x) (x).rbegin(), (x).rend()
#define in(v, s) ((s).find((v)) != (s).end())
#define GCD(x, y) __gcd(abs((x)), abs((y)))

#define INF (LLONG_MAX>>3ll)
#define MOD (1'000'000'007ll)

#define mxN (100'010ll)

inline void maxa(ll &a, ll b) { if (a<b) a=b; }
inline void mina(ll &a, ll b) { if (a>b) a=b; }

ll n;
vc<vcll> gr(mxN);
vcll ar(mxN);
vcll par(mxN);

inline void input()
{
	scanf("%lli%lli", &n, &par[1]);
	ll u;
	par[1]=0;
	f0r(u,2,n)
	{
		scanf("%lli%lli", &par[u], &ar[u]);
		gr[par[u]].pb(u);
	}
}

ll eti;

struct TP
{
	vcll occ;
	ll i;
	inline TP() { i=0; }
	inline void push (ll x) { occ.pb(x); }
	inline ll cntless (ll x)
 	{
		while (i<occ.sz() and occ[i]<x) i++;
		return i;
	}
};
umap<ll, TP> tps;
vcll starte(mxN), ende(mxN);

ll build_tree (ll u)
{
	starte[u]=eti++;
	for (ll v:gr[u]) ar[u]+=build_tree(v);
	ende[u]=eti;
	return ar[u];
}

inline void build_tree()
{
	eti=0;
	build_tree(1);
}

umapll all, rpath, up, down;
inline void calc_all()
{
	ll i;
	f0r(i,1,n) all[ar[i]]=0;
	f0r(i,1,n) all[ar[i]]++;
}

void calc_up (ll u)
{
	up[u]=rpath[ar[u]];
	rpath[ar[u]]++;
	for (ll v:gr[u]) calc_up(v);
	rpath[ar[u]]--;
}

inline void calc_up() // strictly
{
	ll i;
	f0r(i,1,n) rpath[ar[i]]=0;
	calc_up(1);
}

vc<vc<prll>> qs;

inline void calc_down()
{
	qs.resize(eti+10);
	ll u, j;
	f0r(u,1,n)
	{
		qs[ende[u]].pb({u, 1});
		qs[starte[u]].pb({u, -1});
	}
	f0r(j,0,eti) for (prll &uid:qs[j])
	{
		ll u=uid.fi, id=uid.se;
		ll lastd=down[u];
		down[u] += tps[ar[u]].cntless(j)*id;
	}
}

inline void output()
{
	ll u;
	f0r(u,1,n) printf("%lli\n", all[ar[u]] - up[u] - down[u]);
}

void pushocc (ll u)
{
	tps[ar[u]].push(starte[u]);
	for (ll v:gr[u]) pushocc(v);
}
inline void pushocc () { pushocc(1); }

int main()
{
	cin.tie(0); cout.tie(0);
	ios_base::sync_with_stdio(0);
	srand(time(0));

	// freopen("file.in", "r", stdin);
	freopen("conflicts.in", "r", stdin);
	freopen("conflicts.out", "w", stdout);

	input();
	build_tree();
	pushocc();
	calc_all();
	calc_up();
	calc_down();
	output();

	return 0;
}