import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; public class Main implements Runnable { public static void main(String[] args) { new Thread(null, new Main(), "", 512 * 1024 * 1024).start(); } int N; ArrayList[]g; long[] height=new long[200000]; int[] dp2=new int[200000]; class Edge { int v; long cost; public Edge(int v, long cost) { this.v=v; this.cost=cost; } } long ans=0; void dfs(int v, int p) { for(Edge e:g[v]) { if(e.v==p)continue; dfs(e.v,v); height[v]=Math.max(height[v], height[e.v]+e.cost); } } void dfs2(int v, int p, long up) { long[]L=new long[g[v].size()]; long[]R=new long[g[v].size()+1]; for(int i=0;i0)L[i]=L[i-1]; Edge e=g[v].get(i); int u=e.v; if(u==p)continue; L[i]=Math.max(L[i], height[u]+e.cost); } for(int i=g[v].size()-1;i>=0;--i) { R[i]=R[i+1]; Edge e=g[v].get(i); int u=e.v; if(u==p)continue; R[i]=Math.max(R[i], height[u]+e.cost); } for(int i=0;i(); for(int i=0;i