25/9/13 [F - Visible Buildings](https://atcoder.jp/contests/abc385/tasks/abc385_f):卡精度題，若用$O(n)$解法就不會遇到? 25/9/14 [F - Count Arrays](https://atcoder.jp/contests/abc387/tasks/abc387_f):觀察+基環樹 25/9/23 [D. Segments Covering](https://codeforces.com/contest/2125/problem/D):痾就機率dp，可我不會 25/10/4 [E. Distance to Different](https://codeforces.com/contest/1989/problem/E):🉐dp 25/10/6 [E. Ancient Tree](https://codeforces.com/contest/2127/problem/E):要虛樹，可我不會，改天再來學，但我會啟發式合併 25/10/8 [D. Price Tags](https://codeforces.com/contest/2144/problem/D):竟還叫gpt5幫忙debug 25/10/12 ~~我會vim了(h, j, k, l)，但寫code的速度卻比vs code慢~~ 複習以前所學 [非嚴格次小生成樹](https://zerojudge.tw/ShowProblem?problemid=c495) :::spoiler code ```cpp=1 #include<bits/stdc++.h> using namespace std; #define ll long long #define int ll const int mxN=1e5; vector<pair<int, int>> adj[mxN]; int mx[21][mxN], p[mxN], jmp[21][mxN], dep[mxN]; int find(int x) { if(x^p[x]) { return p[x]=find(p[x]); } return x; } bool unite(int a, int b) { int x=find(a), y=find(b); if(x^y) { p[x]=y; return 1; } return 0; } int lca(int a, int b) { if(dep[a]<dep[b]) swap(a, b); int diff=dep[a]-dep[b]; for(int i=20; ~i; i--) { if(diff>>i&1) { a=jmp[i][a]; } } if(a==b) return a; for(int i=20; ~i; i--) { if(jmp[i][a]!=jmp[i][b]) { a=jmp[i][a]; b=jmp[i][b]; } } return jmp[0][a]; } void dfs(int v, int fa) { dep[v]=(~fa?dep[fa]:-1)+1; jmp[0][v]=fa; for(int i=1; i<=20; i++) { if(jmp[i-1][v]==-1) break; jmp[i][v]=jmp[i-1][jmp[i-1][v]]; mx[i][v]=max(mx[i-1][v], mx[i-1][jmp[i-1][v]]); } for(auto [u, w] : adj[v]) { if(u==fa) continue; mx[0][u]=w; dfs(u, v); } } int f(int a, int b) { int res=0; int c=lca(a, b); int diff=dep[a]-dep[c]; for(int i=20; ~i; i--) { if(diff>>i&1) { res=max(res, mx[i][a]); a=jmp[i][a]; } } diff=dep[b]-dep[c]; for(int i=20; ~i; i--) { if(diff>>i&1) { res=max(res, mx[i][b]); b=jmp[i][b]; } } return res; } int32_t main() { ios::sync_with_stdio(0); cin.tie(0); int n, m; cin>>n>>m; iota(p, p+n, 0); vector<array<int, 3>> edge; vector<bool> e(m); for(int i=0; i<m; i++) { int a, b, w; cin>>a>>b>>w; --a, --b; edge.push_back({w, a, b}); } sort(edge.begin(), edge.end()); int cnt=0, idx=0; int sum=0; while(cnt<n-1) { auto [w, x, y]=edge[idx]; if(unite(x, y)) { cnt++; adj[x].push_back({y, w}); adj[y].push_back({x, w}); e[idx]=1; sum+=w; } idx++; } memset(jmp, -1, sizeof(jmp)); dfs(0, -1); int ans=1e18; for(int i=0; i<m; i++) { if(!e[i]) { ans=min(ans, sum-f(edge[i][1], edge[i][2])+edge[i][0]); } } cout<<sum<<' '<<ans<<"\n"; return 0; } ``` ::: [嚴格次小生成樹](https://loj.ac/p/10133) ::: spoiler code ```cpp=1 //小心維護mx1 #include<bits/stdc++.h> using namespace std; #define ll long long #define int ll const int mxN=1e5; vector<pair<int, int>> adj[mxN]; int mx[21][mxN], mx1[21][mxN], p[mxN], jmp[21][mxN], dep[mxN]; int find(int x) { if(x^p[x]) { return p[x]=find(p[x]); } return x; } bool unite(int a, int b) { int x=find(a), y=find(b); if(x^y) { p[x]=y; return 1; } return 0; } int lca(int a, int b) { if(dep[a]<dep[b]) swap(a, b); int diff=dep[a]-dep[b]; for(int i=20; ~i; i--) { if(diff>>i&1) { a=jmp[i][a]; } } if(a==b) return a; for(int i=20; ~i; i--) { if(jmp[i][a]!=jmp[i][b]) { a=jmp[i][a]; b=jmp[i][b]; } } return jmp[0][a]; } void dfs(int v, int fa) { dep[v]=(~fa?dep[fa]:-1)+1; jmp[0][v]=fa; for(int i=1; i<=20; i++) { if(jmp[i-1][v]==-1) break; jmp[i][v]=jmp[i-1][jmp[i-1][v]]; mx[i][v]=max(mx[i-1][v], mx[i-1][jmp[i-1][v]]); if(mx[i-1][v]==mx[i-1][jmp[i-1][v]]) { mx1[i][v]=max(mx1[i-1][v], mx1[i-1][jmp[i-1][v]]); } else { if(mx[i][v]==mx[i-1][v]) { mx1[i][v]=mx[i-1][jmp[i-1][v]]; } else { mx1[i][v]=mx[i-1][v]; } } } for(auto [u, w] : adj[v]) { if(u==fa) continue; mx[0][u]=w; dfs(u, v); } } int f(int a, int b, int w) { int res=0; int c=lca(a, b); int diff=dep[a]-dep[c]; for(int i=20; ~i; i--) { if(diff>>i&1) { res=max(res, (w!=mx[i][a]?mx[i][a]:mx1[i][a])); a=jmp[i][a]; } } diff=dep[b]-dep[c]; for(int i=20; ~i; i--) { if(diff>>i&1) { res=max(res, (w!=mx[i][b]?mx[i][b]:mx1[i][b])); b=jmp[i][b]; } } return res; } int32_t main() { ios::sync_with_stdio(0); cin.tie(0); int n, m; cin>>n>>m; iota(p, p+n, 0); vector<array<int, 3>> edge; vector<bool> e(m); for(int i=0; i<m; i++) { int a, b, w; cin>>a>>b>>w; --a, --b; edge.push_back({w, a, b}); } sort(edge.begin(), edge.end()); int cnt=0, idx=0; int sum=0; while(cnt<n-1) { auto [w, x, y]=edge[idx]; if(unite(x, y)) { cnt++; adj[x].push_back({y, w}); adj[y].push_back({x, w}); e[idx]=1; sum+=w; } idx++; } memset(jmp, -1, sizeof(jmp)); dfs(0, -1); int ans=1e18; for(int i=0; i<m; i++) { if(!e[i]) { ans=min(ans, sum-f(edge[i][1], edge[i][2], edge[i][0])+edge[i][0]); } } cout<<ans<<"\n"; return 0; } ``` ::: 25/10/24 [E. Anton and Permutation](https://codeforces.com/contest/785/problem/E):經典分塊題，可惡bug好煩，先擺著 25/10/28 [F - Loud Cicada](https://atcoder.jp/contests/abc423/tasks/abc423_f):數學題，好像要用到二項式反演，但我會容斥，最後跟它好像有異曲同工之妙? 25/10/30 [G - Fine Triplets](https://atcoder.jp/contests/abc392/tasks/abc392_g):模板題，但值得注意```while(len<=2*mx) len*=2```要取等號，因為當兩個數都等於$mx$時數組會越界，~~CSES沒卡我~~ 25/11/02 [F - Dangerous Sugoroku](https://atcoder.jp/contests/abc388/tasks/abc388_f):這題我沒想到，其實就只用到矩陣快速冪而已，看完題解後我就直覺地做，跑了1秒多過了，題解還在搞優化，雖然快了不少，但我沒理解，改天再看看吧，~~因該不會看反正都過了~~ 25/11/04 [E. New Year and Castle Construction](https://codeforces.com/contest/1284/problem/E):亂找的，但好像是計算幾何，先放在這，我要去補眠了 25/11/08 [F - Variety Split Hard](https://atcoder.jp/contests/abc397/tasks/abc397_f):水題?純粹我遇到第二次[類似題](https://atcoder.jp/contests/dp/tasks/dp_w)還想不到要從供獻下手 25/11/9 [F - Jump Traveling](https://atcoder.jp/contests/abc414/tasks/abc414_f):觀察+bfs 25/11/10 [APIO 2007 Zoo](https://cses.fi/237/list/):狀壓dp，然後我不會，先放在這 [P3403 跳楼机](https://www.luogu.com.cn/problem/P3403):複習同餘最短路，注意h要先減1 25/11/11 [E - Reflection on Grid](https://atcoder.jp/contests/abc431/tasks/abc431_e):類似Jump Traveling，然後狀態不要懶得開 25/11/13 [Two Stack Sorting](http://cses.fi/problemset/task/2402) 25/11/17 [C - Nearest vectors](https://codeforces.com/contest/598/problem/C):又是計算幾何 25/11/22 [F - Double Sum 3](https://atcoder.jp/contests/abc390/tasks/abc390_f):又是供獻老梗，可惜我沒解開qq 25/11/23 [E. Best Subsequence](https://codeforces.com/contest/2026/problem/E):想不到這題要用網路流 25/11/25 [G - Leaf Color](https://atcoder.jp/contests/abc340/tasks/abc340_g):這題嗆我不會dp和找bug 25/12/09 [F - Two Sequence Queries](https://atcoder.jp/contests/abc357/tasks/abc357_f):線段樹模板題，但我真的找不到bug😢 [ 987 . 最大子正方形和](https://oj.ntucpc.org/contests/25/problems/987):巨水? 25/12/10 [Ex - 01? Queries](https://atcoder.jp/contests/abc246/tasks/abc246_h):ctrl c ctrl v，dp+快速冪，~~我好懶~~ 25/12/14 [IOI13_CAVE](https://oj.uz/problem/view/IOI13_cave):譴責不會二分搜 25/12/20 [E. A, B, AB and BA](https://codeforces.com/contest/2069/problem/E):我不會貪心 25/12/22 [G. Xor-MST](https://codeforces.com/contest/888/problem/G):複習boruvka，另外第一次被卡，unordered_map常數真的很大 25/12/25 [G - Alone](https://atcoder.jp/contests/abc346/tasks/abc346_g):線段樹應用，然後我的code寫爛沒考慮到極端的情況，導致一直wa一筆測資 [Feast (NOI19_feast)](https://oj.uz/problem/view/NOI19_feast):複習alien優化 25/12/28 [NOI18_knapsack](https://oj.uz/problem/view/NOI18_knapsack):從5月困擾我到現在才ac的題，記得當時就以為只是多重背包水題，然後傳上去只有73，複雜度是$O(N \log K)$，但注意到本題$S<=2000$，往$S$沒有很大想一下，均攤後，複雜度可降到$O(S^2 \log S)$ 25/12/29 [F - Exhausted?](https://atcoder.jp/contests/arc076/tasks/arc076_d):hall theorem 25/12/31 [C. Watching Fireworks is Fun](https://codeforces.com/contest/372/problem/C):Happy New Year! 單調dp(順便複習單調優化多重背包問題，~~有點通靈，我比賽時一定想不到~~) 25/1/1 [Game (IOI13_game)](https://oj.uz/problem/view/IOI13_game):這題我是用二維線段樹加動態開點做，然後就MLE了，只拿到63，後來，空間優化我實在想不到，看了wiwiho的[code](https://oj.uz/submission/423041)後，我才發現可以用懶標，感性理解一下，均攤空間(有這講法嗎?)，就會發現優化了很大的空間，然後就過了(外傳:因為這題，我從偽指標使用者(因為若用此方法，只能拿到80，雖然大陸好像用了四分樹解決，但我不會)，所以我就轉為了指標使用者XD) 25/1/4 [部落衝突 2](https://toj.tfcis.org/oj/pro/1059/):南一中的複賽題，精神ac一下，有兩種做法，離線(用lca)或在線(用hld) [G - Mediator](https://atcoder.jp/contests/abc350/tasks/abc350_g):分塊輕重點 [J. First Non-Bipartite Edge](https://codeforces.com/edu/course/2/lesson/7/2/practice/contest/289391/problem/J):二分圖判定(水)，用dsu 25/1/6 [Snake Escaping](https://oj.uz/problem/view/JOI18_snake_escaping):先擺著，我只想到22分的暴力，滿分解要用到sos dp(超集合&子集合) 25/1/13 [D - Non-Ancestor Matching](https://atcoder.jp/contests/arc205/tasks/arc205_d):我code寫爛的題 25/1/15 [APIO 2007 backup](https://cses.fi/237/task/B/):又是code寫爛的題，只好叫gemini 3幫我debug QAQ [D - Switch Seats](https://atcoder.jp/contests/abc399/tasks/abc399_d):又是code寫爛的題，先放著反正也才900 25/1/23 好久沒更新~ [E. Fair Share](https://codeforces.com/problemset/problem/1634/E):想不到歐拉迴路如何套在此題上，看題解精神一下，簡單說一下，就是發現數字出現次數若為奇數則無解，否則必存在解，將每組看成點放在集合A，並將點連向每組中的數值，跑一下歐拉迴路，就好了 25/2/6 [Meteors (POI11_met)](https://oj.uz/problem/view/POI11_met):問LLM了解整體二分思想(我賽中一定想不到XD)