QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#864899#4408. 燃烧的呐球12345678900 0ms0kbC++1413.3kb2025-01-21 10:56:092025-01-21 10:56:10

Judging History

你现在查看的是最新测评结果

  • [2025-01-21 10:56:10]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2025-01-21 10:56:09]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ll int
#define mp make_pair
#define inf (ll)1e9
#define pii pair <ll, ll>
#define fr first
#define se second
const ll mod = 1e9 + 7;
char buf[1 << 21], *p1 = buf, *p2 = buf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 18, stdin), p1 == p2) ? EOF : *p1++)
inline ll read() {
	ll x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9') f = ((ch == '-') ? -1 : f), ch = getchar();
	while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
	return x * f;
}
inline void write(long long x) {
	if(x < 0) x = -x, putchar('-');
	if(x >= 10) write(x / 10);
	putchar(x % 10 + '0');
}
long long Ans;
ll n, m, Rtt;
ll Fa[1000005], siz[1000005];
vector <ll> G[1000005], V0[1000005], V1[1000005];
struct Pa {
	ll x, y;
}p[100005];
ll dfn[1000005], pos[1000005], posr[1000005], son[1000005], tot; 
inline void dfs(ll x) {
	dfn[++tot] = x, pos[x] = tot;
	siz[x] = 1;
	for(auto y : G[x]) {
		dfs(y);
		siz[x] += siz[y]; 
		if(siz[y] > siz[son[x]]) son[x] = y;
	}
	posr[x] = tot;
}

struct UnionSet {
	ll fa[100005];
	inline void makeSet(ll x) {
		for(ll i = 1; i <= x; i++) fa[i] = i;
	}
	inline ll findSet(ll x) {
		if(x == fa[x]) return x;
		return fa[x] = findSet(fa[x]);
	}
	inline void unionSet(ll x, ll y) {
		x = findSet(x), y = findSet(y);
		if(x == y) return ;
		fa[x] = y;
	}
}U;
inline bool chk() {
	for(ll i = 2; i <= m; i++) if(U.findSet(i) != U.findSet(1)) return 1;
	return 0;
}
pii lk[1000005];
inline void Mn(ll i, ll j, ll val) {
	if(U.findSet(i) == U.findSet(j) || !j) return ; 
	if(val < lk[i].fr) lk[i].fr = val, lk[i].se = j;
}
inline void upd(pii &mn, pii &mnse, ll val, ll i) {
	if(!i) return ;
	if(val < mn.fr) {
		if(U.findSet(i) != U.findSet(mn.se)) mnse = mn;
		mn = mp(val, i);
	}
	else if(U.findSet(i) != U.findSet(mn.se) && val < mnse.fr) mnse = mp(val, i);	
}

struct BST {
	#define ls(x) sn[x][0]
	#define rs(x) sn[x][1]
	ll sn[1000005][2], fa[1000005], lsiz[1000005];
	pii amn[1000005], amnse[1000005];
	pii mn[1000005], mnse[1000005];
	ll sta[4000005], top;
	pii tmpmn[4000005], tmpmnse[4000005];
	pii tmpamn[4000005], tmpamnse[4000005];
	inline ll buildline(ll l, ll r) {
		if(l > r) return 0;
		if(l == r) return sta[l];
		
		ll ssiz = 0, cnt = 0;
		for(ll i = l; i <= r; i++) ssiz += lsiz[sta[i]];
		for(ll i = l; i <= r; i++) {
			cnt += lsiz[sta[i]];
			if(2 * cnt >= ssiz) {
				ll lson = buildline(l, i - 1), rson = buildline(i + 1, r);
				fa[lson] = fa[rson] = sta[i];
				ls(sta[i]) = lson, rs(sta[i]) = rson;
				return sta[i];
			}
		}
		return 0;
	}
	inline ll build(ll x) {
		for(ll i = x; i; i = son[i]) lsiz[i] = siz[i] - siz[son[i]];
		for(ll i = x; i; i = son[i]) {
			for(auto y : G[i]) {
				if(!lsiz[y]) {
					ll Son = build(y);
					fa[Son] = i; 
				}
			} 
		}
		top = 0;
		for(ll i = x; i; i = son[i]) sta[++top] = i;
		return buildline(1, top);
	} 
	inline ll isson(ll x) {
		return (ls(fa[x]) == x || rs(fa[x]) == x);
	}
	inline void Save(ll x) {
		sta[++top] = x, tmpmn[top] = mn[x], tmpmnse[top] = mnse[x], tmpamn[top] = amn[x], tmpamnse[top] = amnse[x];
	}
	inline void Insert(ll x, ll val, ll id) {
		Save(x);
		upd(amn[x], amnse[x], val, id);
		upd(mn[x], mnse[x], val, id);
		for(ll i = x; i; i = fa[i]) {
			if(!fa[i] || !isson(i)) return ;
			Save(fa[i]);
			upd(mn[fa[i]], mnse[fa[i]], mn[i].fr, mn[i].se);
			upd(mn[fa[i]], mnse[fa[i]], mnse[i].fr, mnse[i].se);
		}
	}
	pii Mn, Mnse;
	inline void Get_ans(ll x) {
		Mn = Mnse = mp(inf, 0);
		upd(Mn, Mnse, amn[x].fr, amn[x].se);
		upd(Mn, Mnse, amnse[x].fr, amnse[x].se);
		if(ls(x)) {
			upd(Mn, Mnse, mn[ls(x)].fr, mn[ls(x)].se);
			upd(Mn, Mnse, mnse[ls(x)].fr, mnse[ls(x)].se);	
		}
		for(ll i = x; i; i = fa[i]) {
			if(fa[i] && i != ls(fa[i])) {
				upd(Mn, Mnse, amn[fa[i]].fr, amn[fa[i]].se);
				upd(Mn, Mnse, amnse[fa[i]].fr, amnse[fa[i]].se);
				if(ls(fa[i])) {
					upd(Mn, Mnse, mn[ls(fa[i])].fr, mn[ls(fa[i])].se);
					upd(Mn, Mnse, mnse[ls(fa[i])].fr, mnse[ls(fa[i])].se);	
				}
			}	
		}
	}
	inline void Back(ll x) {
		while(top > x) {
			mn[sta[top]] = tmpmn[top], mnse[sta[top]] = tmpmnse[top];
			amn[sta[top]] = tmpamn[top], amnse[sta[top]] = tmpamnse[top];
			top--;
		}
	}
}BT;

namespace Sub1 {
	pii mn, mnse;
	inline void init() {
		mn = mnse = mp(inf, 0);
		for(ll i = 1; i <= m; i++) {
			ll val = siz[p[i].x] + siz[p[i].y];
			upd(mn, mnse, val, i);
		}
	}
	inline void solve() {
		for(ll i = 1; i <= m; i++) {
			Mn(i, mn.se, siz[p[i].x] + siz[p[i].y] + mn.fr);
			Mn(i, mnse.se, siz[p[i].x] + siz[p[i].y] + mnse.fr);
		}
	}
};
//+xi+yi +xj+yj

namespace Sub2 {
	pii mnx[1000005], mnsex[1000005];
	pii mny[1000005], mnsey[1000005];
	inline void dfs2(ll x) {
		mnx[x] = mnsex[x] = mp(inf, 0);
		mny[x] = mnsey[x] = mp(inf, 0);
		
		for(auto i : V0[x]) upd(mnx[x], mnsex[x], -siz[p[i].x] + siz[p[i].y], i);
		for(auto i : V1[x]) upd(mny[x], mnsey[x], siz[p[i].x] - siz[p[i].y], i);
		for(auto y : G[x]) {
			dfs2(y);
			upd(mnx[x], mnsex[x], mnx[y].fr, mnx[y].se);
			upd(mnx[x], mnsex[x], mnsex[y].fr, mnsex[y].se);
			upd(mny[x], mnsey[x], mny[y].fr, mny[y].se);
			upd(mny[x], mnsey[x], mnsey[y].fr, mnsey[y].se);
		}
	}
	inline void init() {
		for(ll t = n; t >= 1; t--) {
			ll x = dfn[t];
			mnx[x] = mnsex[x] = mp(inf, 0);
			mny[x] = mnsey[x] = mp(inf, 0);
			
			for(auto i : V0[x]) upd(mnx[x], mnsex[x], -siz[p[i].x] + siz[p[i].y], i);
			for(auto i : V1[x]) upd(mny[x], mnsey[x], siz[p[i].x] - siz[p[i].y], i);
			for(auto y : G[x]) {
				upd(mnx[x], mnsex[x], mnx[y].fr, mnx[y].se);
				upd(mnx[x], mnsex[x], mnsex[y].fr, mnsex[y].se);
				upd(mny[x], mnsey[x], mny[y].fr, mny[y].se);
				upd(mny[x], mnsey[x], mnsey[y].fr, mnsey[y].se);
			}
		}
	}
	inline void dfs22(ll x) {
		for(auto i : V0[x]) {
			Mn(i, mnx[x].se, mnx[x].fr + siz[p[i].x] + siz[p[i].y]);
			Mn(i, mnsex[x].se, mnsex[x].fr + siz[p[i].x] + siz[p[i].y]);
		}
		for(auto i : V1[x]) {
			Mn(i, mny[x].se, mny[x].fr + siz[p[i].x] + siz[p[i].y]);
			Mn(i, mnsey[x].se, mnsey[x].fr + siz[p[i].x] + siz[p[i].y]);
		}
		for(auto y : G[x]) dfs22(y);
	}
	inline void solve() {
		dfs22(1);
	}
};
//+xi+yi -xj+yj
//+xi+yi +xj-yj

namespace Sub3 {
	pii mnx[1000005], mnsex[1000005];
	pii mny[1000005], mnsey[1000005];
	ll cntx, cnty;
	inline void init() {
		cntx = cnty = 0;
		mnx[0] = mnsex[0] = mny[0] = mnsey[0] = mp(inf, 0);
	}
	inline void dfs3(ll x) {
		cntx++, cnty++;
		mnx[cntx] = mnx[cntx-1], mnsex[cntx] = mnsex[cntx-1];
		mny[cnty] = mny[cnty-1], mnsey[cnty] = mnsey[cnty-1];
		for(auto i : V0[x]) upd(mnx[cntx], mnsex[cntx], siz[p[i].x] + siz[p[i].y], i);
		for(auto i : V1[x]) upd(mny[cnty], mnsey[cnty], siz[p[i].x] + siz[p[i].y], i);
		for(auto i : V0[x]) {
			Mn(i, mnx[cntx].se, mnx[cntx].fr - siz[p[i].x] + siz[p[i].y]);
			Mn(i, mnsex[cntx].se, mnsex[cntx].fr - siz[p[i].x] + siz[p[i].y]);
		}
		for(auto i : V1[x]) {
			Mn(i, mny[cnty].se, mny[cnty].fr + siz[p[i].x] - siz[p[i].y]);
			Mn(i, mnsey[cnty].se, mnsey[cnty].fr + siz[p[i].x] - siz[p[i].y]);
		}
		for(auto y : G[x]) dfs3(y);
		cntx--, cnty--;
	}
	inline void solve() {
		dfs3(1);
	}
};
//-xi+yi +xj+yj
//+xi-yi +xj+yj

namespace Sub4 {
	struct Seg_Tree {
		ll sta[4000005], top;
		struct st {
			ll l, r;
			pii mn, mnse;
		}t[4000005], lst[4000005]; 
		inline void Back(ll x) {
			while(top > x) t[sta[top]] = lst[top], top--; 
		}
		inline void build(ll id, ll l, ll r) {
			t[id].l = l, t[id].r = r;
			t[id].mn = t[id].mnse = mp(inf, 0);
			if(l == r) return ;
			ll mid = (l + r) >> 1;
			build(id << 1, l, mid);
			build(id << 1 | 1, mid + 1, r);
		}
		inline void push_up(ll id) {
			t[id].mn = t[id << 1].mn, t[id].mnse = t[id << 1].mnse;
			upd(t[id].mn, t[id].mnse, t[id << 1 | 1].mn.fr, t[id << 1 | 1].mn.se);
			upd(t[id].mn, t[id].mnse, t[id << 1 | 1].mnse.fr, t[id << 1 | 1].mnse.se);
		}
		inline void update(ll id, ll x, ll val, ll i) {
			sta[++top] = id, lst[top] = t[id];
			if(t[id].l == t[id].r) {
				upd(t[id].mn, t[id].mnse, val, i);
				return ;
			}
			ll mid = (t[id].l + t[id].r) / 2;
			if(x <= mid) update(id << 1, x, val, i);
			else update(id << 1 | 1, x, val, i);
			push_up(id);
		}
		pii mn, mnse;
		inline void get_ans(ll id, ll L, ll R) {
			if(L <= t[id].l && t[id].r <= R) {
				upd(mn, mnse, t[id].mn.fr, t[id].mn.se);
				upd(mn, mnse, t[id].mnse.fr, t[id].mnse.se);
				return ;
			}
			ll mid = (t[id].l + t[id].r) >> 1;
			if(L <= mid) get_ans(id << 1, L, R);
			if(R > mid) get_ans(id << 1 | 1, L, R);
		} 
		inline void Get_ans(ll L, ll R) {
			mn = mnse = mp(inf, 0);
			get_ans(1, L, R);
		}
	}Tx, Ty; 
	inline void init() {
		Tx.build(1, 1, n), Ty.build(1, 1, n);
	}
	inline void dfs4(ll x) {
		ll topx = Tx.top, topy = Ty.top;
		for(auto i : V0[x]) Tx.update(1, pos[p[i].y], siz[p[i].x] - siz[p[i].y], i);
		for(auto i : V1[x]) Ty.update(1, pos[p[i].x], -siz[p[i].x] + siz[p[i].y], i); 
		for(auto i : V0[x]) {
			Tx.Get_ans(pos[p[i].y], posr[p[i].y]);
			Mn(i, Tx.mn.se, Tx.mn.fr - siz[p[i].x] + siz[p[i].y]);
			Mn(i, Tx.mnse.se, Tx.mnse.fr - siz[p[i].x] + siz[p[i].y]);
		}
		for(auto i : V1[x]) {
			Ty.Get_ans(pos[p[i].x], posr[p[i].x]);
			Mn(i, Ty.mn.se, Ty.mn.fr + siz[p[i].x] - siz[p[i].y]);
			Mn(i, Ty.mnse.se, Ty.mnse.fr + siz[p[i].x] - siz[p[i].y]);		
		}
		for(auto y : G[x]) dfs4(y);
		Tx.Back(topx), Ty.Back(topy);
	}
	inline void solve() {
		dfs4(1);
	}
};
//-xi+yi +xj-yj
//+xi-yi -xj+yj

namespace Sub5 {
	ll rt[1000005];
	struct Seg_Tree {
		struct st {
			ll l, r;
			pii mn, mnse;
		}t[4000005]; 
		ll cnt;
		inline void push_up(ll id) {
			if(!t[id].l) t[id].mn = t[t[id].r].mn, t[id].mnse = t[t[id].r].mnse;
			else {
				t[id].mn = t[t[id].l].mn, t[id].mnse = t[t[id].l].mnse;
				if(t[id].r) {
					upd(t[id].mn, t[id].mnse, t[t[id].r].mn.fr, t[t[id].r].mn.se);
					upd(t[id].mn, t[id].mnse, t[t[id].r].mnse.fr, t[t[id].r].mnse.se);	
				}	
			}
		}
		pii mn, mnse;
		inline void insert(ll &id, ll l, ll r, ll x, ll val, ll i) {
			if(!id) id = ++cnt, t[id].mn = t[id].mnse = mp(inf, 0), t[id].l = t[id].r = 0;
			if(l == r) {
				upd(t[id].mn, t[id].mnse, val, i);
				return ;
			}
			ll mid = (l + r) >> 1;
			if(x <= mid) insert(t[id].l, l, mid, x, val, i);
			else insert(t[id].r, mid + 1, r, x, val, i);
			push_up(id);
		}
		inline ll Merge(ll u, ll v, ll l, ll r) {
			if(!u || !v) return u + v;
			if(l == r) {
				upd(t[u].mn, t[u].mnse, t[v].mn.fr, t[v].mn.se);
				upd(t[u].mn, t[u].mnse, t[v].mnse.fr, t[v].mnse.se);
				return u;
			}
			ll mid = (l + r) >> 1;
			t[u].l = Merge(t[u].l, t[v].l, l, mid);
			t[u].r = Merge(t[u].r, t[v].r, mid + 1, r);
			push_up(u);
			return u;
		} 
		inline void get_ans(ll id, ll l, ll r, ll L, ll R) {
			if(!id) return ;
			if(L <= l && r <= R) {
				upd(mn, mnse, t[id].mn.fr, t[id].mn.se);
				upd(mn, mnse, t[id].mnse.fr, t[id].mnse.se);
				return ;
			}
			ll mid = (l + r) >> 1;
			if(L <= mid) get_ans(t[id].l, l, mid, L, R);
			if(R > mid) get_ans(t[id].r, mid + 1, r, L, R);
		}
		inline void Get_ans(ll Rt, ll L, ll R) {
			mn = mnse = mp(inf, 0);
			get_ans(Rt, 1, n, L, R);
		}
	}T;
	inline void init() {
		T.cnt = 0;
		for(ll i = 1; i <= n; i++) rt[i] = 0;
	}
	inline void dfs5(ll x) {
		for(auto i : V0[x]) T.insert(rt[x], 1, n, pos[p[i].y], -siz[p[i].x] - siz[p[i].y], i);
		for(auto y : G[x]) {
			dfs5(y);
			rt[x] = T.Merge(rt[x], rt[y], 1, n);
		}
		for(auto i : V0[x]) {
			T.Get_ans(rt[x], pos[p[i].y], posr[p[i].y]);
			Mn(i, T.mn.se, T.mn.fr + siz[p[i].x] + siz[p[i].y]);
			Mn(i, T.mnse.se, T.mnse.fr + siz[p[i].x] + siz[p[i].y]);
		}
	}
	inline void solve() {
		dfs5(1);
	}
};
//+xi+yi -xj-yj

namespace Sub6 {
	inline void init() {
		for(ll i = 1; i <= n; i++) BT.mn[i] = BT.mnse[i] = BT.amn[i] = BT.amnse[i] = mp(inf, 0);
		BT.top = 0;
	}
	inline void dfs6(ll x) {
		ll lst = BT.top;
		for(auto i : V0[x]) BT.Insert(p[i].y, siz[p[i].x] + siz[p[i].y], i);
		for(auto i : V0[x]) {
			BT.Get_ans(p[i].y);
			Mn(i, BT.Mn.se, BT.Mn.fr - siz[p[i].x] - siz[p[i].y]);
			Mn(i, BT.Mnse.se, BT.Mnse.fr - siz[p[i].x] - siz[p[i].y]);	
		}
		for(auto y : G[x]) dfs6(y);
		BT.Back(lst);
	}
	inline void solve() {
		dfs6(1);
	}
};
//-xi-yi +xj+yj

inline void Clear() {
	for(ll i = 1; i <= m; i++) lk[i] = mp(inf, 0);
}
/*
xi yi
xj yj
*/

inline void Boruvka() {
	Clear();
	Sub1 :: init(), Sub1 :: solve();
	Sub2 :: init(), Sub2 :: solve();
	Sub3 :: init(), Sub3 :: solve();
	Sub4 :: init(), Sub4 :: solve();
	Sub5 :: init(), Sub5 :: solve();
	Sub6 :: init(), Sub6 :: solve();
	
	for(ll i = 1; i <= m; i++) {
		ll j = U.findSet(i);
		if(lk[i].fr < lk[j].fr) lk[j] = lk[i];
	} 
	for(ll i = 1; i <= m; i++) {
		if(U.findSet(i) == i) {
			ll j = lk[i].se;
			if(!j) continue;
			if(U.findSet(j) != i) U.unionSet(i, j), Ans += lk[i].fr; 
		}
	}
}
int main() {
	freopen("1.in", "r", stdin);
//	freopen("mine.out", "w", stdout);
	n = read(), m = read();
	U.makeSet(m);
	for(ll i = 2; i <= n; i++) {
		Fa[i] = read();
		G[Fa[i]].push_back(i);
	}
	for(ll i = 1; i <= m; i++) {
		p[i].x = read(), p[i].y = read();
		V0[p[i].x].push_back(i);
		V1[p[i].y].push_back(i);
	}
	dfs(1);
	Rtt = BT.build(1);
	while(chk()) Boruvka();
	write(Ans), putchar('\n');
	return 0;
}
/*
8 2
1 2 3 1 5 4 3 
8 4
3 2

8 3
1 2 3 1 5 4 3 
8 4
4 1
3 2
*/

详细

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

score: 0
Time Limit Exceeded

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Time Limit Exceeded

Test #16:

score: 0
Time Limit Exceeded

Subtask #5:

score: 0
Time Limit Exceeded

Test #21:

score: 0
Time Limit Exceeded

Subtask #6:

score: 0
Time Limit Exceeded

Test #26:

score: 0
Time Limit Exceeded

Subtask #7:

score: 0
Skipped

Dependency #1:

0%