結果
| 問題 |
No.3113 The farthest point
|
| ユーザー |
 anago-pie
|
| 提出日時 | 2025-07-26 04:03:26 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 892 ms / 2,000 ms |
| コード長 | 16,276 bytes |
| コンパイル時間 | 3,558 ms |
| コンパイル使用メモリ | 317,388 KB |
| 実行使用メモリ | 79,124 KB |
| 最終ジャッジ日時 | 2025-07-26 04:03:53 |
| 合計ジャッジ時間 | 19,344 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 33 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<n; i++)
#define debug 0
#define YES cout << "Yes" << endl;
#define NO cout << "No" << endl;
using ll = long long;
using ld = long double;
const int mod = 998244353;
const int MOD = 1000000007;
const double pi = atan2(0, -1);
const int inf = 1 << 31 - 1;
const ll INF = 1LL << 63-1;
#include <time.h>
#include <chrono>
//vectorの中身を空白区切りで出力
template<typename T>
void print1(vector<T> v) {
for (int i = 0; i < v.size(); i++) {
cout << v[i];
if (i < v.size() - 1) {
cout << " ";
}
}
}
//vectorの中身を改行区切りで出力
template<typename T>
void print2(vector<T> v) {
for (auto x : v) {
cout << x << endl;
}
}
//二次元配列を出力
template<typename T>
void printvv(vector<vector<T>> vv) {
for (vector<T> v : vv) {
print1(v);
cout << endl;
}
}
//vectorを降順にソート
template<typename T>
void rsort(vector<T> &v) {
sort(v.begin(), v.end());
reverse(v.begin(), v.end());
}
//昇順priority_queueを召喚
template<typename T>
struct rpriority_queue {
priority_queue<T, vector<T>, greater<T>> 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<int> prime (int n) {
vector<bool> ch(n, false);
vector<int> 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<double> X, vector<double> Y, vector<double>Z) {
vector<double> x = { X[0] - Y[0],X[1] - Y[1] };
vector<double> 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<int> min_prime_list;
int upper_limit;
osa_k(int N) {
//N:最大値。一つの自然数の素因数分解にしか興味が泣ければそれを入力
vector<int> 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<int> devPrimes(int n) {
vector<int> 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<vector<Edge>> 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<bool> 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<tuple<int, int, ll>> flowing_edges() {
vector<tuple<int, int, ll>> 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<vector<Edge>> Graph;
Edge& rev_Edge(Edge& edge) {
return Graph[edge.to][edge.rev];
}
vector<int> 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<int> 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<tuple<int, int, ll>> flowing_edges(){
vector<tuple<int,int,ll>> 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 <typename T>
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<node> 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){
k-=tmp;
now=tree[now].cr;
}
else{
now=tree[now].cl;
}
}
else{
int tmp=0;
if(tree[now].cl==-1){
now=tree[now].cr;
}
else if(tree[now].cr==-1){
now=tree[now].cl;
}
else{
if(tree[tree[now].cl].size>=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){
k-=tmp;
now=tree[now].cl;
}
else{
now=tree[now].cr;
}
}
else{
int tmp=0;
if(tree[now].cr==-1){
now=tree[now].cl;
}
else if(tree[now].cl==-1){
now=tree[now].cr;
}
else{
if(tree[tree[now].cr].size>=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<val){
if(tree[now].cl!=-1){
ret+=tree[tree[now].cl].size;
}
now=tree[now].cr;
}
else{
now=tree[now].cl;
}
}
return ret;
}
int lower_or_equal_count(T val){
//val以下の値の個数を返す
int ret=0;
int now=root;
while(now!=-1){
if(tree[now].val<=val){
if(tree[now].cl!=-1){
ret+=tree[tree[now].cl].size;
}
if(tree[now].survive){
ret++;
}
now=tree[now].cr;
}
else{
now=tree[now].cl;
}
}
return ret;
}
int upper_count(T val){
//valより大きい値の個数を返す
return tree[root].size - lower_or_equal_count(val);
}
int upper_or_equal_count(T val){
//val以上の値の個数を返す
return tree[root].size - lower_count(val);
}
};
int main(){
int N;
cin>>N;
vector<vector<int>> path(N);
map<int,map<int,ll>> 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<vector<int>> child(N);
vector<bool> check(N,false);
function<void(int)> 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<vector<ll>> score(N,{0});
function<void(int)> 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<<ans<<endl;
}