#include using namespace std; #define rep(i, n) for(int i=0; i #include //vectorの中身を空白区切りで出力 template void print1(vector v) { for (int i = 0; i < v.size(); i++) { cout << v[i]; if (i < v.size() - 1) { cout << " "; } } } //vectorの中身を改行区切りで出力 template void print2(vector v) { for (auto x : v) { cout << x << endl; } } //二次元配列を出力 template void printvv(vector> vv) { for (vector v : vv) { print1(v); cout << endl; } } //vectorを降順にソート template void rsort(vector &v) { sort(v.begin(), v.end()); reverse(v.begin(), v.end()); } //昇順priority_queueを召喚 template struct rpriority_queue { priority_queue, greater> pq; void push(T x) { pq.push(x); } void pop() { pq.pop(); } T top() { return pq.top(); } size_t size() { return pq.size(); } bool empty() { return pq.empty(); } }; //高速10^n計算(mod mod) ll tenth(int n) { if (n == 0) { return 1; } else if (n % 2 == 0) { ll x = tenth(n / 2); x %= mod; x *= x; x %= mod; return x; } else { ll x = tenth(n - 1); x *= 10; x %= mod; return x; } } //高速a^n計算 ll power(int a, int n){ if(n == 0){ return 1; } else if(n % 2 == 0){ ll x = power(a, n / 2); x *= x; return x; } else { ll x = power(a, n - 1); x *= a; return x; } } //n以下の素数列を生成 vector prime (int n) { vector ch(n, false); vector pr; for(int i = 2; i <= n; i++){ if(!ch[i]){ pr.push_back(i); for(int j = 1; i*j<=n; j++){ ch[i*j]=true; } } } return pr; } //最大公約数(ユークリッドの互除法) ll gcd (ll a, ll b){ if(b>a){ swap(a, b); } while(a%b!=0){ ll t = a; a = b; b = t%b; } return b; } //最小公倍数(gcdを定義しておく) ll lcm (ll a, ll b){ ll g = gcd(a, b); ll x = (a/g)*b; return x; } //角XYZ(偏角Z→X)の角度([0,2π)) double angle(vector X, vector Y, vectorZ) { vector x = { X[0] - Y[0],X[1] - Y[1] }; vector z = { Z[0] - Y[0],Z[1] - Y[1] }; double pre, post; pre = atan2(x[1], x[0]); post = atan2(z[1], z[0]); if (post < 0) { post += pi*2; } if (pre < 0) { pre += pi*2; } if (pre < post) { pre += pi * 2; } return pre - post; } //mod mod下で逆元を算出する //高速a^n計算(mod ver.) ll mypower(ll a, ll n, ll Mod=mod) { if (n == 0) { return 1; } else if (n % 2 == 0) { ll x = mypower(a, n / 2,Mod); x *= x; x %= Mod; return x; } else { ll x = mypower(a, n - 1,Mod); x *= a; x %= Mod; return x; } } //フェルマーの小定理を利用 ll modinv(ll p, ll Mod=mod) { return mypower(p, Mod - 2,Mod) % Mod; } ////素因数分解(osa_k法)(前計算O(N)、素数判定O(1)、素因数分解(O(logN)) //エラトステネスの篩の代わりとしても使える(N項のvectorを生成するため、巨大数に対しては√Nまでの素数リストを作って割る方が良い) struct osa_k { //最大値までの各自然数に対し、その最小の素因数を格納するリスト vector min_prime_list; int upper_limit; osa_k(int N) { //N:最大値。一つの自然数の素因数分解にしか興味が泣ければそれを入力 vector v(N + 1); upper_limit = N; rep(i, N + 1) { v[i] = i; } swap(min_prime_list, v); //k=2から見る for (int k = 2; k * k <= N; k++) { if (min_prime_list[k] == k) { //最小の素因数=自分ならば、素数 //kが素数の時、t=k*kから始めてt=Nまでのkの倍数全てを確認する。未更新の自然数があれば、それの最小の素因数をkに更新する。 //k*k未満のkの倍数に対しては、kが最小の素因数にはなり得ないので計算する必要が無い for (int t = k * k; t <= N; t += k) { if (min_prime_list[t] == t) { min_prime_list[t] = k; } } } } } //任意の自然数nが素数であればtrueを返す bool isPrime(int n) { if (n < 2) { return false; } else { return min_prime_list[n] == n; } } //任意の自然数nの素因数分解を行う。素因数はvectorで与えられる(ex:n=12 -> {2,2,3}) vector devPrimes(int n) { vector vec; int now = n; while (now > 1) { vec.push_back(min_prime_list[now]); now /= min_prime_list[now]; } return vec; } }; //最大流問題を解く構造体(Ford-Fulkerson法.O(FE)) struct maxflow { struct Edge { int to, rev; ll capacity, init_capacity; int off, on; Edge(int _to, int _rev, ll _capacity, int _off, int _on) :to(_to), rev(_rev), capacity(_capacity), init_capacity(_capacity), off(_off), on(_on) {}; }; int delay=0; vector> Graph; maxflow(int MAX_V, int d) { Graph.assign(MAX_V, {}); delay=d; } void input(int from, int to, ll capacity, int off, int on) { int e_id = Graph[from].size(); int r_id = Graph[to].size(); Graph[from].push_back(Edge(to, r_id, capacity, off, on)); Graph[to].push_back(Edge(from, e_id, 0, on+delay, off-delay)); } Edge& rev_Edge(Edge& edge) { return Graph[edge.to][edge.rev]; } vector visited; ll dfs(int now, int g, ll flow, int time) { visited[now] = true; if (now == g) { return flow; } else { ll f = 0; ll res_flow = flow; for (Edge& edge : Graph[now]) { if (!visited[edge.to] && edge.capacity > 0 && edge.off>=time && edge.on<=1e9) { ll f_delta = dfs(edge.to, g, min(res_flow, edge.capacity), edge.on+delay); edge.capacity -= f_delta; rev_Edge(edge).capacity += f_delta; f += f_delta; res_flow -= f_delta; if (res_flow == 0) { break; } } } return f; } } void flowing(int s, int g, ll init_flow = INF) { bool cont = true; while (cont) { visited.assign(Graph.size(), false); ll flow = dfs(s, g, init_flow,0); init_flow -= flow; if (flow == 0) { cont = false; } } } ll get_flow(int g) { ll flow = 0; for (Edge& edge : Graph[g]) { Edge& rev_edge = rev_Edge(edge); ll tmp_flow = rev_edge.init_capacity - rev_edge.capacity; if (tmp_flow > 0) { flow += tmp_flow; } } return flow; } vector> flowing_edges() { vector> vec; rep(from, Graph.size()) { for (Edge& edge : Graph[from]) { ll flow = edge.init_capacity - edge.capacity; if (flow > 0) { vec.push_back({ from,edge.to,flow }); } } } return vec; } }; //Dinic法でのmax-flow。最大マッチングなど辺のキャパシティが小さい場合には高速 struct Dinic { struct Edge { int to, rev; ll capacity, init_capacity; ld cost; Edge(int _to, int _rev, ll _capacity,ld _cost) :to(_to), rev(_rev), capacity(_capacity),init_capacity(_capacity),cost(_cost) {}; }; vector> Graph; Edge& rev_Edge(Edge& edge) { return Graph[edge.to][edge.rev]; } vector level,itr; Dinic(int MAX_V) { Graph.assign(MAX_V, {}); } void input(int _from, int _to, ll _capacity,ld _cost) { int e_id = Graph[_from].size(), r_id = Graph[_to].size(); Graph[_from].push_back(Edge(_to, r_id, _capacity,_cost)); Graph[_to].push_back(Edge(_from, e_id, 0LL,_cost)); } void bfs(int s, int g, ld val) { level.assign(Graph.size(), -1); level[s] = 0; queue q; q.push(s); while (!q.empty()) { int now = q.front(); q.pop(); if (now == g) { continue; } for (Edge &e : Graph[now]) { if (level[e.to] == -1 && e.capacity > 0 && e.cost<=val) { level[e.to] = level[now] + 1; q.push(e.to); } } } } ll dfs(int now, int g, ll flow, ld val) { if (now == g) { return flow; } else if (level[now] >= level[g]) { return 0; //gよりも深い場所に行こうとしたら終わり。flow=0を返す } else { ll res_flow = flow; ll f = 0; for (int &i = itr[now]; i < Graph[now].size(); i++) { Edge& edge = Graph[now][i]; if (level[edge.to] == level[now] + 1 && edge.capacity > 0 && edge.cost<=val) { ll f_delta = dfs(edge.to, g, min(res_flow, edge.capacity), val); edge.capacity -= f_delta; rev_Edge(edge).capacity += f_delta; res_flow -= f_delta; f += f_delta; if (res_flow == 0) { break; } } } return f; //行先が無い場合はflow=0を返す } } void flowing(int s, int g, ll init_flow = INF, ld val=0) { bool cont1 = true; while (cont1) { bfs(s, g,val); if (level[g] == -1) { cont1 = false; } else { bool cont2 = true; while (cont2) { itr.assign(Graph.size(), 0); ll flow = dfs(s, g, init_flow,val); init_flow -= flow; if (flow == 0) { cont2 = false; } } } if(init_flow==0){ cont1=false; } } } ll get_flow(int g) { ll flow = 0; for (Edge& edge : Graph[g]) { flow += max(0LL, rev_Edge(edge).init_capacity - rev_Edge(edge).capacity); } return flow; } vector> flowing_edges(){ vector> vec; for (int from = 0; from < Graph.size(); from++) { for (Edge& edge : Graph[from]) { if (edge.init_capacity - edge.capacity > 0) { vec.push_back({ from,edge.to,edge.init_capacity - edge.capacity }); } } } return vec; } void reset() { for (int from = 0; from < Graph.size(); from++) { for (Edge& edge : Graph[from]) { edge.capacity = edge.init_capacity; } } } }; //小さい方/大きい方からk番目の値を取り出せる平衡二分木 template struct ordered_set{ struct node{ T val; //載せたい値。不等式で順序が定義されるものにする int prio; //優先度(ランダムに付与される。平衡化するために必要) int id; //この頂点のindex int par; //親のindex int cl; //子の内小さい方のindex int cr; //子の内大きい方のindex int size; //この頂点を根とする部分木の大きさ bool survive; //eraseされたらfalseになる node(int _val=0,int _id=-1, int _par=-1, int _cl=-1, int _cr=-1){ val=_val; id=_id; prio=rand(); par=_par; cl=_cl; cr=_cr; size=1; survive=true; } }; vector tree; int root; ordered_set(){ srand(int(time(NULL))); tree={}; root=-1; } int size(){ return root==-1?0:tree[root].size; } int calc_size(node &n){ int ret=1; if(n.cl!=-1){ ret+=tree[n.cl].size; } if(n.cr!=-1){ ret+=tree[n.cr].size; } n.size=ret; return ret; } int find(T val){ int now=root; while(now!=-1){ if(tree[now].val==val){ break; } if(tree[now].val>=val){ now=tree[now].cl; } else{ now=tree[now].cr; } } return now; } bool count(T val){ int id=find(val); if(id==-1 || !tree[id].survive){ return false; } else{ return true; } } bool empty(){ return size()==0; } void rotate(node &c, node &p){ if(p.par!=-1){ if(tree[p.par].cl==p.id){ tree[p.par].cl=c.id; } else{ tree[p.par].cr=c.id; } } if(c.val<=p.val){ if(c.cr!=-1){ tree[c.cr].par=p.id; } p.cl=c.cr; c.cr=p.id; c.par=p.par; p.par=c.id; } else{ if(c.cl!=-1){ tree[c.cl].par=p.id; } p.cr=c.cl; c.cl=p.id; c.par=p.par; p.par=c.id; } calc_size(p); } void add_child(node &c, node &p){ c.par=p.id; if(c.val<=p.val){ p.cl=c.id; } else{ p.cr=c.id; } p.size++; } bool insert(T val){ int id=find(val); if(id==-1){ tree.push_back(node(val, tree.size())); node &neo=tree[tree.size()-1]; if(root==-1){ root=neo.id; } else{ int p=root; while(true){ tree[p].size++; int c; if(tree[p].val>=val){ c=tree[p].cl; } else{ c=tree[p].cr; } if(c!=-1){ p=c; } else{ break; } } add_child(neo, tree[p]); while(neo.par!=-1){ if(tree[neo.par].prio>neo.prio){ break; } else{ rotate(neo, tree[neo.par]); } } calc_size(neo); if(neo.par==-1){ root=neo.id; } } return true; } else if(tree[id].survive){ return false; } else { tree[id].survive=true; int now=id; while(now!=-1){ tree[now].size++; now=tree[now].par; } return true; } } bool erase(T val){ int id=find(val); if(id==-1){ return false; } else if(!tree[id].survive){ return false; } else{ tree[id].survive=false; int now=id; while(now!=-1){ tree[now].size--; now=tree[now].par; } return true; } } T find_kth_min(int k){ assert(k<=size()); int now=root; while(true){ if(tree[now].survive){ int tmp=1; if(tree[now].cl!=-1){ tmp+=tree[tree[now].cl].size; } if(tmp==k){ break; } else if(tmp=k){ now=tree[now].cl; } else{ k-=tree[tree[now].cl].size; now=tree[now].cr; } } } } return tree[now].val; } T find_kth_max(int k){ assert(k<=size()); int now=root; while(true){ if(tree[now].survive){ int tmp=1; if(tree[now].cr!=-1){ tmp+=tree[tree[now].cr].size; } if(tmp==k){ break; } else if(tmp=k){ now=tree[now].cr; } else{ k-=tree[tree[now].cr].size; now=tree[now].cl; } } } } return tree[now].val; } int lower_count(T val){ //valより小さい値の個数を返す int ret=0; int now=root; while(now!=-1){ if(tree[now].val>N; vector> path(N); map> cost; rep(i,N-1){ int u,v; ll c; cin>>u>>v>>c; u--; v--; path[u].push_back(v); path[v].push_back(u); cost[u][v]=c; cost[v][u]=c; } ll ans=0; vector> child(N); vector check(N,false); function make_tree=[&](int now){ for(int x:path[now]){ if(!check[x]){ check[x]=true; child[now].push_back(x); make_tree(x); } } }; check[0]=true; vector> score(N,{0}); function solve=[&](int now){ for(int c:child[now]){ solve(c); score[now].push_back(score[c][0]+cost[now][c]); } if(score[now].size()>=2){ rsort(score[now]); ans=max(ans, score[now][0]+score[now][1]); } }; make_tree(0); solve(0); cout<