### atcoder_official's blog

By atcoder_official, history, 4 weeks ago,

We will hold Denso Create Programming Contest 2024（AtCoder Beginner Contest 361）.

We are looking forward to your participation!

• +128

 » 4 weeks ago, # |   -105 Contest Topic Predictions for ABC:A will be brute force.B,C and D will be a Graph/Segment Tree/Advanced DP Problem/BS on answers/Sweepline.E,F and G will be advanced data structures, MST, ternary search, NP Hard and 3 SAT problem.
•  » » 4 weeks ago, # ^ |   +2 Aged like milk
 » 4 weeks ago, # |   -48 Plz dont organise contest by Denso hereafter. Bring Back Suntory contests.
 » 4 weeks ago, # | ← Rev. 3 →   -15 If I still can't solve till I open problem D, I may really cry.
 » 4 weeks ago, # |   -10 GL & HFHope E.
•  » » 4 weeks ago, # ^ |   -25 Hello, I'm a primary school student, too. I live in Dalian Development Zone!
 » 4 weeks ago, # |   -33 Are there any Chinese?
•  » » 4 weeks ago, # ^ |   -30 Here.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   -27 HereEdit: Guys why the downvotes??
•  » » » 4 weeks ago, # ^ |   -17 Here
•  » » » » 4 weeks ago, # ^ |   -17 Here
•  » » 4 weeks ago, # ^ |   -11 Hnist
•  » » 4 weeks ago, # ^ |   -17 here
 » 4 weeks ago, # |   -23 qpqp
 » 4 weeks ago, # |   -16 I couldn't solve problem B any more! Because my maths is terrible, I couldn't imagine those cubiods' location!
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +10 Disclaimer: contest is over now so we are allowed to discuss solutions.Define a boolean function $f(x_1, y_1, x_2, y_2)$ to be true if the ranges $(x1, y1)$ and $(x2, y2)$ intersect. (Take note of the open intervals).Then, the two cuboids intersect if and only if $f(a, d, g, j)$, $f(b, e, h, k)$ and $f(c, f, i, l)$ are all true.My (messy) solution. I find it funny how I solved the problems in the order A CDEF B.
 » 4 weeks ago, # |   0 Is F a known problem? I was sure I'd find code for it somewhere online but could only find a paper on it.
•  » » 4 weeks ago, # ^ |   +1
•  » » 4 weeks ago, # ^ |   0 I think problem F is almost the same (or an eaiser version) as this one https://mirror.codeforces.com/contest/955/problem/C , and you can check the editorial of that contest, https://mirror.codeforces.com/blog/entry/58547I was lucky because I just solved this problem at codeforces several weeks ago, when I took a virtual participation of that contest. Solving as many problems as possible is really important, and you will benefit from it sooner or later!
 » 4 weeks ago, # |   0 This solution for F gives WA for 2 test cases,can anyone help?
•  » » 4 weeks ago, # ^ |   0 me too, can you help me with this submission (2 testcases only): https://atcoder.jp/contests/abc361/submissions/55314240
•  » » » 4 weeks ago, # ^ |   0 The function pow() in cmath header is not overflow safe (it can cause overflows), so better use a manual powering function.This modified code of yours now works in 1ms ! :)
 » 4 weeks ago, # |   0 This was a great contest, enjoyed all problems and this is my first time solving A-F. B was a bit annoying tho.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Me too. I regretted skipping B because it added a lot of time to my penalty :((I did the problems in the order A CDEF B)
•  » » » 4 weeks ago, # ^ |   0 is this your alt acc,i mean reaching upto F and still a newbie doesnt make sense to me
•  » » » » 4 weeks ago, # ^ |   0 No, my accounts on both Codeforces and AtCoder are jatrophalouvre, but my accounts are very new (I created them around two weeks ago) so my ratings are not accurate yet.
•  » » » 4 weeks ago, # ^ |   0 AtCoder penalty time is the maximum submission time, not their (weighted) sum. The order doesn't matter if you solve the same set of problems.
 » 4 weeks ago, # |   0 This contest was easier than usual, hmmm?
 » 4 weeks ago, # |   0 Oh my godThere is an original problem
 » 4 weeks ago, # | ← Rev. 2 →   +8 My logic for E was as follows: The optimal path will start from a leaf and end at another leaf. Let's say the two optimal leaves are a and b, and their LCA (lowest common ancestor is) c, then all the edges in the tree will be traversed twice except the ones between a and c, and b and c. Hence we want to maximise the sum of those edges. For this I iterated over all the vertices assuming them as LCA and found out the maximum value of highest depth. See my code for more details: https://atcoder.jp/contests/abc361/submissions/55306890But I'm getting Wrong Answer on 5 test cases. Can anyone help me find out the issue here?Update: Found the error. I needed to use multiset instead of set
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +2 The answer can be calculated as each edge weight * 2 minus the weighted diameter of the tree
•  » » 4 weeks ago, # ^ |   0 My ideas was for each node i to find the maximum distance to some other node denoted by ans[i] . Now if I start from u, the answer will be 2 * ( sum of all edge weight ) — ans[u] . We need to return the minimum . JAVA : TLE C++ : AC
 » 4 weeks ago, # |   -10 B and C were bad, and I am surprised to see those many submissions on them. I really feel the dumbest.
 » 4 weeks ago, # |   0 D cooked me ,time to focus on implementation
 » 4 weeks ago, # |   0 how to solve d?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 D is a brute force search problem. I did double-ended BFS. It is a bit overkill but I used this because I didn't want to TLE, although I've seen normal BFS work too.Edit: downvoters please explain?
•  » » » 4 weeks ago, # ^ |   0 could you please explain ?? with your code ?
•  » » » » 4 weeks ago, # ^ | ← Rev. 3 →   0 I wrote a normal BFS solution as well. I will be using this code because it is easier to understand. However, the prerequisites are that you understand and know how to apply BFS algorithms. If not, a simple search will suffice.Starting with main(), we first cin>>n>>st>>te. To make our lives easier, we add ".." to the end of st and te. Now that we have initialized our start and goal states, we carry out bfs().Moving onto bfs(), the first line should be fairly obvious: if st==te then we clearly return 0. Otherwise, we start with some more initializing.unordered_map d tracks the distance from st, i.e. d[s] is the minimal number of operations required to get from st to s. Then, we want to find d[te].unordered_map vis tracks whether we have already processed a string, i.e. if vis[s]=1, then we have already processed s, and we shall not process s again.queue q is the standard BFS queue. Actually, all of these initializing things should make sense if you know BFS.The main idea of the BFS is that we start from a string u and brute force every string v that can be reached from u in 1 operation. To do this, we first add st to q, set d[st]=0 and vis[st]=1. These should be self-explanatory.Then, to find all strings v that can be reached from u in 1 operation, we first initialize an integer pos, which is the position of the gaps, i.e. $u[pos]=u[pos+1]='.'$. Now that we know the gaps, we brute force swapping every adjacent characters with $[pos, pos+1]$. We do this by looping from i=0 to i=u.size()-2. Note that we don't loop to i=u.size()-1, because then i+1 will be out of range of u. We need some additional if conditionals to ensure that the intervals Unable to parse markup [type=CF_MATHJAX] and $[pos, pos+1]$ don't overlap.Then, to swap $[i, i+1]$ and $[pos, pos+1]$, simply taking swap(v[i], v[pos]) and swap(v[i+1], v[pos+1]) suffices. The rest are all standard BFS procedures.
•  » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 hello can u help me in debugging my it's not working for 3rd test case int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; cin>>n; string s; cin>>s; string t; cin>>t; mapmp; if(s==t){ cout<<0; } else{ s.push_back('.'); s.push_back('.'); t.push_back('.'); t.push_back('.'); mapvis; multiset>>mm; mm.insert({0,{s,n}}); mp[s]=0; vis[s]=1; while(mm.size()!=0){ auto vv=*mm.begin(); int xx=vv.first; string sn=vv.second.first; int nn=vv.second.second; mm.erase(mm.begin()); //mm.pop(); vis[sn]=1; for(int i=0;i<=n;i++){ if(i==nn){ continue; } if(i==nn+1){ continue; } if(i==nn-1){ continue; } string s2=sn; swap(s2[i],s2[nn]); swap(s2[i+1],s2[nn+1]); if(vis[s2]==0){ mm.insert({xx+1,{s2,i}}); mp[s2]=xx+1; vis[s2]=1; } } } if(mp[t]==0){ cout<<-1; } else{ cout<
 » 4 weeks ago, # |   0 how to do f?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Use principle of inclusion exclusion with prime exponents up to 60 (since 2^60>10^18).This is my solution: https://atcoder.jp/contests/abc361/submissions/55309609
•  » » 4 weeks ago, # ^ |   0 In C++ it is actually possible to just store every a^b with b>=3 in a set and check that stored value is not a square of some other number by finding an integer square root. Only caveat is to use binary search for finding an integer square root to avoid precision issues. Answer is int_sqrt(n) + set size.
 » 4 weeks ago, # | ← Rev. 3 →   0 luck for me,is can be ac! (problem D) #include #define pii pair #define int long long #define rep(i, j, n) for (int i = (int)(j); i <= (int)(n); i++) #define endl '\n' using namespace std; const int Mod = 1e9 + 7; inline int add(int a, const int &b){ a += b — Mod; a += (a>>31) & Mod; return a; } inline void usub(int &a, const int &b){ a -= b; a += (a>>31) & Mod; } inline int sub(int a, const int &b){ a -= b, a += (a>>31) & Mod; return a; } inline void umul(int &a, const int &b){ a = (int)(1ll * a * b % Mod); } inline int mul(const int &a, const int &b){ return (int)(1ll * a * b % Mod); } int qpow(int b, int p){ int ret = 1; while(p){ if(p & 1) umul(ret, b); umul(b, b), p >>= 1; } return ret; } // priority_queue, less> q; char c[20],c1[20]; int n; int aws=100000000000000000; int vis[20]; bool j(){ rep(i,1,n){ if(c[i]!=c1[i]){ return false; } } return true; } void dfs(int p,int lay){ if(j()){ aws=min(aws,lay); } if(lay>8){ return; } rep(i,lay-1,n-1){ if(c[i]!='.'&&c[i+1]!='.'&&vis[i]==0){ swap(c[i],c[p]); swap(c[i+1],c[p+1]); vis[i]=1; dfs(i,lay+1); vis[i]=0; swap(c[i],c[p]); swap(c[i+1],c[p+1]); } } } void solve() { cin>>n; int ct1=0,ct2=0,ct3=0,ct4=0; rep(i,1,n){ cin>>c[i]; ct1+=(c[i]=='B'); ct2+=(c[i]=='W'); } rep(i,1,n){ cin>>c1[i]; ct3+=(c1[i]=='B'); ct4+=(c1[i]=='W'); } if(ct1==ct3&&ct2==ct4){ n++; c[n]='.'; c1[n]='.'; n++; c[n]='.'; c1[n]='.'; dfs(n-1,0); cout<<(aws == 100000000000000000 ? -1:aws); } else{ cout<<-1; } } int32_t main() { ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); // int t; // cin >> t; // while (t--){ solve(); //} return 0; } // 
 » 4 weeks ago, # | ← Rev. 3 →   0 What is wrong with this solution in C? #include #include #include #include #include #pragma GCC optimize ("O3") #pragma GCC target ("sse4") #define all(x) x.begin(),x.end() using namespace std; void paveway(){ long long n , k; cin >> n >> k; vector a(n); long long mn = 10000000000 , mx = -10000000000; for(long long i = 0; i < n; i++) cin >> a[i]; sort(all(a)); if(!( k % 2)){ for(ll i = (k / 2)-1; i < (n - (i + 1)); i++){ mn = min(mn , a[i]); mx = max(mx , a[i]); } cout << mx - mn << endl ; }else{ for(long long i = (k/2)+1;i < (n - ((k/2))); i++){ mn = min(mn , a[i]); mx = max(mx , a[i]); } cout << mx - mn << endl; } } int main (){ ios::sync_with_stdio(false); cin.tie(nullptr); long long t = 1; //long long t; cin >> t; for(;t--;) paveway(); return 0; } 
•  » » 4 weeks ago, # ^ |   0 For this testcase Spoilerk=3 and arr=1 3 8 100 101 102 your code gives 93, but answer is 2
 » 4 weeks ago, # |   0 Why this time abc361 have a same problem with luogu(an oj in China)?The same problem in luogu: https://www.luogu.com.cn/problem/P9118There is a discuss in luogu recently: https://www.luogu.com.cn/discuss/845537
•  » » 4 weeks ago, # ^ |   0 Disappointing, I was pretty sure the problem wasn't original but couldn't find the solution for it using an english search engine.
 » 4 weeks ago, # |   0 The problem F is an original problem.A lot of people do it.
 » 4 weeks ago, # |   0 Solved ABCF, D and E were harder than F
 » 4 weeks ago, # |   0 Is F based on Mobius Function? I believe F is Inclusion-Exclusion, but could not figure out which values to include/exclude in time.
•  » » 4 weeks ago, # ^ |   0 Yes it is.
•  » » 4 weeks ago, # ^ |   +6 You don't need any advanced knowledge for F. Just try to optimize the brute force. There is ~$10^6$ values of x where $b \geq 3$ so you can track those values in a set to avoid overcounting. For $b = 2$ binary search on the biggest square that is less or equal to $N$. My submission: https://atcoder.jp/contests/abc361/submissions/55297768
•  » » 4 weeks ago, # ^ |   +5 It is kind of smart brute force. Firstly we will count the number of values such that $i^2<=N$ . After this, we have to count the cubes and higher power. For doing this we can just start a loop from $2$ till $\sqrt[3]{n}$ . We must take care to not overcount elements, for example $64$ which is both the square of 8 and the cube of 2
•  » » 4 weeks ago, # ^ |   +5 You can do it using Inclusion-Exclusion too. You've to basically count all squares, cubes, a^4,.. a^k less than N. Iterate from highest power to lowest power and find those values (using kth root). Then for each power k you've to exclude calculated value of its multiples.
•  » » » 2 weeks ago, # ^ |   0 can u explain how to count squares, cubes, a^4,.. a^k with kth root ??
•  » » » » 2 weeks ago, # ^ |   0 The amount of k-th powers from 1 to N is floor(N^(1/k)).
•  » » » » 2 weeks ago, # ^ | ← Rev. 2 →   0 Count of a^k from 1 to n is a^(1/k). You can calculate kth root using binary search, it's a pretty standard problem you can google it. Take care of the edge case when a^k exceeds long long range. Here's a link to my submission.
 » 4 weeks ago, # |   0 can anyone please help me with this: https://atcoder.jp/contests/abc361/submissions/55314240? I'm getting WA on two tests, even though my code passed for 1 and 1e18
 » 4 weeks ago, # | ← Rev. 2 →   0 There's an exactly same problem from the National Olympics in Informatics (Spring Contest, 2023) in China, even the samples are same (original sample #3->sample #1, original sample #4->sample #3). Is it a concidence?
 » 4 weeks ago, # |   0 https://www.luogu.com.cn/problem/P9118 You know that F is an known problem,but you don't know that this problem is a pro version of F.
 » 4 weeks ago, # |   0 Solved ABCD，problem B is funny
•  » » 4 weeks ago, # ^ |   0 how to solve D ?
 » 4 weeks ago, # | ← Rev. 3 →   0 This is the code for question B, only one test point did not pass. Can anyone provide me with a set of hack data? #include #include #include #include #include #include #include #include #include #define endl "\n" typedef long long LL; using std::cin; using std::cout; using std::getline; using std::max; using std::min; using std::sort; using std::vector; using std::string; using std::stringstream; using std::queue; using std::priority_queue; using std::map; using std::stack; struct Node { int x, y, z; }; vector pii; int main() { int x, y, z, a, b, c; int xx, yy, zz, aa, bb, cc; cin >> x >> y >> z >> a >> b >> c; xx = x; yy = y; zz = z; aa = a; bb = b; cc = c; pii.push_back({x, y, z}); pii.push_back({a, y, z}); pii.push_back({x, y, c}); pii.push_back({a, y, c}); pii.push_back({a, b, c}); pii.push_back({x, b, c}); pii.push_back({x, b, z}); pii.push_back({a, b, z}); cin >> x >> y >> z >> a >> b >> c; pii.push_back({x, y, z}); pii.push_back({a, y, z}); pii.push_back({x, y, c}); pii.push_back({a, y, c}); pii.push_back({a, b, c}); pii.push_back({x, b, c}); pii.push_back({x, b, z}); pii.push_back({a, b, z}); bool ok = false; if (a == aa && b == bb && c == cc && x == xx && y == yy && z == zz) ok = true; int cccc = 0; for (int i = 0; i < 8; i ++) { Node now = pii[i]; if (now.x > min(x, a) && now.x < max(x, a) && now.y > min(y, b) && now.y < max(y, b) && now.z > min(z, c) && now.z < max(z, c)) { ok = true; } } if ((xx < a && yy < b && zz < c && aa >= a && bb >= b && cc >= c) || (x < aa && y < bb && z < cc && a >= aa && b >= bb && c >= cc)) ok = true; x = xx; y = yy; z = zz; a = aa; b = bb; c = cc; for (int i = 8; i < 16; i ++) { Node now = pii[i]; if (now.x > min(x, a) && now.x < max(x, a) && now.y > min(y, b) && now.y < max(y, b) && now.z > min(z, c) && now.z < max(z, c)) { ok = true; } } if (ok) cout << "Yes" << endl; else cout << "No" << endl; return 0; } /* */ 
•  » » 4 weeks ago, # ^ |   0 1 1 1 3 3 3 1 1 1 2 4 4 
 » 4 weeks ago, # |   +3 Is there an explanation as to why G isn't commonly included in official editorials?
 » 4 weeks ago, # | ← Rev. 3 →   0 I noticed a strange behaviour in c++ today while writing code for problem D. When I use & sign before "it" in the code, the output is some gibberish like "��q{xU"  ll n = 16; string s = "BBBWBWWWBBWWBW.."; queue>q; q.push({n,s}); while(!q.empty()){ ll sz = q.size(); while(sz--){ auto &it = q.front(); q.pop(); ll pos = it.first; string str = it.second; cout<<"str = "<
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 You use & when you want a reference to the value. i.e. for (auto & i : v) i++; will increase all elements in a vector, while for(auto i : v) i++; will not affect the original vector. You are getting a reference to the front of your queue, then removing the front, so you may get some garbage because you're referencing something that doesn't exist.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 What you are saying is true and I agree with you. However, this issue only happens when string length is >15. I tried for various lengths <=15 and it works in those cases. Do you have any explanation for that ?
 » 4 weeks ago, # |   0 If anyone could tell me the idea for G that would be great. I tried the following:First, we clearly just want to find all enclosed areas. Let pair f[i] denote the coordinates of the i-th stone. Then, we connect a (bidirectional) edge from $u$ to $v$ if |f[u].first-f[v].first|<=1 and |f[u].second-f[v].second|<=1. Then, an enclosed area is analogous to a cycle in this graph. If we have a cycle $a_1, a_2, \dots, a_n$ in this graph, we can calculate the number of lattice points enclosed by the polygon formed by f[a[1]], f[a[2]], ..., f[a[n]] by using Pick's Theorem. We can calculate the area using shoelace and "reverse engineer" the number of lattice points enclosed by the polygon using Pick's Theorem. Summation of this should give us the answer.This, however, is giving WA. If anyone could correct me, that would be greatly appreciated.
 » 4 weeks ago, # |   0 Lol, I didn't expect this to work, but F is brute force!F Brute Force
 » 4 weeks ago, # |   +9 Many thanks to yuto1115 for sharing an amazing solution of G — Go Territory (*ˊᗜˋ*)/ᵗᑋᵃᐢᵏ ᵞᵒᵘ*
•  » » 4 weeks ago, # ^ |   +19 I totally agree. During the contest I came up with the original idea (from another editorial) and failed to consider all cases properly. Actually, it took me nearly a dozen of submissions after the contest for all tests to be passed. I was wondering how so many people during the contest did it so fast and clean. After reading about yuto1115's approach I feel really stupid, but now I fully understand how this problem should have been solved during the contest. For sure, one of the most educational problems I've seen so far on AtCoder.
 » 4 weeks ago, # |   0 E is this problem
•  » » 4 weeks ago, # ^ |   0 Isn't it F?
•  » » 3 weeks ago, # ^ |   0 Oops, I meant F
 » 4 weeks ago, # |   0 hey guys. how to solve F?
•  » » 4 weeks ago, # ^ |   0 there is said to be a brute force solution, but i cannot really understand that. my solution is to use dp and inclusion-exclusion principle. first, we can ignore 1 as it is too special. then let f[x] be the number of integars between 1 and N that can be written as pow(p, x). we can calculate it with floor(pow(n, 1/x)) - 1 (you may need to implement bisection method to avoid precision problem with these cmath functions). but there is obviously some duplicated integars calculated. for example, 2^6 is in f[6] while also in f[3] as 4^3. to avoid this, you can substract all f[x*j] from f[x] where j are integars greater than 2. the reason is simple: we calculate an integar only in f[x] where x is the greatest possible. by doing this all f[x] we calculated includes no duplicated integars. we can get the sum of all f[x] as the answer. lastly dont forget the 1 we excluded previously. my code
•  » » » 4 weeks ago, # ^ |   0 thanks! I still don't understand why your solution works. (the inclusion-exclusion part). Can you prove that you're not overcounting (or undercounting) anything?
•  » » » » 4 weeks ago, # ^ |   0 if an integar x is going to be counted, it can be written as p^q, let assune a case where q is the greatest. in another word, if we decompose the prime factors of x, the gcd of all the index of the factors is q. now we can learn that for every integar x there exist an only q which is greatest possible. as 2^60 > 1e18, all the q of the integars we are counting is no greater than 60, so we can enumerate q from 60 to 2. for each m as a factor of q. m < q, x = p^q = (p^(q/m))^m. when we are calculating f[m], such x is also calculated in f[q], so we substract it. and m*j (j>=2) can enumerate all the integars that have a factor m and is greater than m. when m = q, in this case we will not substract f[q] from f[m] because m*j>m. therefore the f[m] remaining includes only x=p^m where m is the greatest and it will make the following recursion holds true. (please forgive my terrible wording as i am not a native english speaker)
•  » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Thanks. It's a beautiful solution! though It took me a while to understand it
•  » » » » 4 weeks ago, # ^ |   0 btw, a similar technique is also performed in this problem (although i think that is much harder)
 » 4 weeks ago, # |   0 I got 2 WA on F, i am not sure whether it is not the correct solution or it is just the precision problem. #include long long n; int mem[10000002]; long long qp(long long p, long long q) { long long r = 1, b = p; while (q) { if (q & 1) r = r * b; b = b * b; q >>= 1; } return r; } long long f(long long x) { if (x == 0) return 0; if (x <= 1e7) { if (mem[x]) return mem[x]; } long long res = 0; for (int i = 2; i <= 61; i ++) { long long l = floor(pow((long double)x, (long double)1.0 / i) + 1e-9); res += l - f(l); }res ++; if (x <= 1e7) mem[x] = res; return res; } signed main(){ std::ios::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0); mem[1] = 1; std::cin >> n; std::cout << f(n); return 0; } 
 » 4 weeks ago, # |   0 Is there any way to know what would their CF rating be?
•  » » 4 weeks ago, # ^ |   0 A-800 B-1000 C-1000 D-1700 E-1700 F-1900 G-2400
•  » » » 4 weeks ago, # ^ |   0 Where did you get them?
 » 4 weeks ago, # |   0 I don't know why Atcoder promotes its contests within Codeforce
 » 4 weeks ago, # |   0 #include using namespace std; const int N = 1e9 + 5; #ifndef ONLINE_JUDGE #include "algo/debug.h" #else #define debug(...) 42 #endif void dfs(int u, int parent, vector> adj[], vector& dist, vector& weight) { for(auto& pair : adj[u]) { int child = pair.first; int wt = pair.second; if(child == parent) { continue; } dist[child] = dist[u] + 1; weight[child] = weight[u] + wt; dfs(child, u, adj, dist, weight); } } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int tt = 1; cin >> tt; while (tt--) { int n; cin >> n; vector> adj[n + 1]; long long totalWeight = 0; for(int i = 0; i < n - 1; i++) { int u, v, w; cin >> u >> v >> w; adj[u].push_back({v, w}); adj[v].push_back({u, w}); totalWeight += w; } vector dist(n + 1); vector weight(n + 1); dfs(1, -1, adj, dist, weight); int oneEnd = -1; long long mxDist = -1; for(int i = 1; i <= n; i++) { mxDist = max(mxDist, dist[i]); } int mxWeight = -1; for(int i = 1; i <= n; i++) { if(mxDist == dist[i]) { if(weight[i] > mxWeight) { oneEnd = i; mxWeight = weight[i]; } } } fill(weight.begin(), weight.end(), 0); dfs(oneEnd, -1, adj, dist, weight); mxWeight = -1; for(int i = 1; i <= n; i++) { mxWeight = max(mxWeight, weight[i]); } cout << (long long)(2 * totalWeight - mxWeight) << "\n"; } return 0; } `Probelm: E I dont know why is this failing for 7 test cases. Can anyone please help...