#if 1 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #ifdef _MSC_VER #pragma warning( push ) #pragma warning( disable : 26450 ) #pragma warning( disable : 26451 ) #pragma warning( disable : 26498 ) #pragma warning( disable : 4459 ) #endif #include #ifdef _MSC_VER #pragma warning( pop ) #endif auto& in = std::cin; auto& out = std::cout; #define all_range(C) std::begin(C), std::end(C) const double PI = 3.141592653589793238462643383279502884197169399375105820974944; constexpr int32_t MAX_N = 600000;//頂点数 constexpr int32_t MAX_LOGN = 30;//log2頂点数 struct edge{ int to; int64_t w; }; std::vector graph[MAX_N];//木 namespace nLCA { int root; // 根ノードの番号 int parent[MAX_LOGN][MAX_N]; // 親を2^k回辿って到達する頂点(根を通り過ぎる場合は-1とする) int depth[MAX_N]; // 根からの深さ int64_t dist[MAX_N]; // 根からの遠さ void dfs(int v, int p, int d, int64_t w) { parent[0][v] = p; depth[v] = d; dist[v] = w; for (int i = 0; i < graph[v].size(); i++) { if (graph[v][i].to != p) dfs(graph[v][i].to, v, d + 1, w + graph[v][i].w); } } // 初期化 void init(int V) { // parent[0]とdepthを初期化する dfs(root, -1, 0, 0); // parentを初期化する for (int k = 0; k + 1 < MAX_LOGN; k++) { for (int v = 0; v < V; v++) { if (parent[k][v] < 0) parent[k + 1][v] = -1; else parent[k + 1][v] = parent[k][parent[k][v]]; } } } // uとvのLCAを求める int glca(int u, int v) { // uとvの深さが同じになるまで親を辿る if (depth[u] > depth[v]) std::swap(u, v); for (int k = 0; k < MAX_LOGN; k++) { if ((depth[v] - depth[u]) >> k & 1) { v = parent[k][v]; } } if (u == v) return u; // 二分探索でLCAを求める for (int k = MAX_LOGN - 1; k >= 0; k--) { if (parent[k][u] != parent[k][v]) { u = parent[k][u]; v = parent[k][v]; } } return parent[0][u]; } std::pair dfs2(int v) { int64_t max1 = 0; int64_t max2 = 0; int64_t max_res = 0; for (int i = 0; i < graph[v].size(); i++) { if (graph[v][i].to != parent[0][v]) { auto new_res = dfs2(graph[v][i].to); max_res = std::max(max_res, new_res.second); auto new_d = new_res.first + graph[v][i].w; if (new_d >= max1) { max2 = max1; max1 = new_d; } else if (new_d >= max2) { max2 = new_d; } } } max_res = std::max(max_res, max1 + max2); return { max1 ,max_res }; } } int32_t N; void input_tree() { in >> N; for (int32_t i = 0; i < N - 1; ++i) { int a, b; int64_t w; in >> a >> b >> w; --a; --b; graph[a].push_back({ b, w }); graph[b].push_back({ a, w }); } } int main() { using std::endl; in.sync_with_stdio(false); out.sync_with_stdio(false); in.tie(nullptr); out.tie(nullptr); input_tree(); nLCA::init(0); auto res = nLCA::dfs2(0); out << res.second << endl; return 0; } #endif #if 0 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #ifdef _MSC_VER #pragma warning( push ) #pragma warning( disable : 26450 ) #pragma warning( disable : 26451 ) #pragma warning( disable : 26498 ) #pragma warning( disable : 4459 ) #endif #include #ifdef _MSC_VER #pragma warning( pop ) #endif auto& in = std::cin; auto& out = std::cout; #define all_range(C) std::begin(C), std::end(C) const double PI = 3.141592653589793238462643383279502884197169399375105820974944; template std::enable_if_t< std::is_unsigned::value, Arithmetic> ipow(Arithmetic bace, Integral n) { //繰り返し二条法 auto res = (Arithmetic)(1); while (n > 0) { if (n & 1) res *= bace; bace *= bace; n >>= 1; } return res; } constexpr bool is_prime(uint32_t N) { if (N <= 1) { return false; } for (size_t i = 2; i * i <= N; ++i) { if (N % i == 0) { return false; } } return true; } template class mint_base; //mint_base_base型用の累乗関数 template constexpr mint_base m_pow(mint_base x, uint64_t n)noexcept; //mod計算を自動で行う整数テンプレートクラス template class mint_base { public: static constexpr auto MOD = MOD_; static_assert(!(MOD <= 2), "MOD cannot be below 2."); static_assert(MOD <= (0xFFFFFFFFFFFFFFFF / 2), "MOD is too big");//加算してオーバーフローしない static_assert(MOD <= 0xFFFFFFFF, "MOD is too big");//乗算してオーバーフローしない constexpr mint_base operator+(const mint_base& other)const noexcept { auto v = *this; return v += other; } constexpr mint_base operator-(const mint_base& other)const noexcept { auto v = *this; return v -= other; } constexpr mint_base operator*(const mint_base& other)const noexcept { auto v = *this; return v *= other; } constexpr auto operator/(const mint_base& other)const noexcept { auto v = *this; return v /= other; } constexpr mint_base& operator+=(const mint_base& other) noexcept { a += other.a; if (MOD <= a) { a -= MOD; }; return *this; } constexpr mint_base& operator-=(const mint_base& other) noexcept { if (a >= other.a) { a -= other.a; } else { a = (a + MOD) - other.a; } return *this; } constexpr mint_base& operator*=(const mint_base& other) noexcept { #if 1 a *= other.a; a %= MOD; #else //MOD <= (MAXUINT64 / 2)条件下 uint64_t b = other.a, v = 0; while (b > 0) { if (b & 1) { v += a; if (v >= MOD)v -= MOD; } a += a; if (MOD <= a)a -= MOD; b >>= 1; } a = v; #endif return *this; } constexpr mint_base& operator/=(const mint_base& other) noexcept { return *this *= ~other; } constexpr mint_base operator+()const noexcept { return *this; } constexpr mint_base operator-()const noexcept { return{ MOD - a, mod_value_tag{} }; } constexpr mint_base& operator++() noexcept { if (MOD <= ++a) { a = 0; }; return *this; } constexpr mint_base& operator--() noexcept { if (a <= 0) { a = MOD; }; --a; return *this; } constexpr mint_base operator++(int) noexcept { auto tmp = *this; ++*this; return tmp; } constexpr mint_base operator--(int) noexcept { auto tmp = *this; --*this; return tmp; } constexpr mint_base operator~()const noexcept { return ipow(*this, e_phi - 1); } constexpr mint_base& operator=(const mint_base& other) noexcept { a = other.a; return *this; } constexpr explicit operator uint64_t()const noexcept { return a; } constexpr explicit operator unsigned()const noexcept { return (unsigned)a; } static constexpr uint64_t getmod() noexcept { return MOD; } constexpr mint_base(uint64_t a_) noexcept :a(a_% MOD) {} constexpr mint_base()noexcept : a(0) {} struct mod_value_tag {}; constexpr mint_base(uint64_t a_, mod_value_tag) :a(a_) {} private: static constexpr uint64_t get_e_phi()noexcept { //オイラー値の導出 uint64_t temp = MOD; uint64_t m_ = MOD; for (uint64_t i = 2; i * i <= m_; ++i) { if (m_ % i == 0) { temp = temp / i * (i - 1); for (; m_ % i == 0; m_ /= i); } } if (m_ != 1)temp = temp / m_ * (m_ - 1); return temp; } static constexpr uint64_t e_phi = get_e_phi();//オイラー値 uint64_t a; }; //mint_base型用の累乗関数 templateconstexpr mint_base m_pow(mint_base x, uint64_t n)noexcept { mint_base res = 1; while (n > 0) { if (n & 1)res *= x; x *= x; n >>= 1; } return res; } //mint_baseの階乗計算 //O(x)時間が必要のため、fact_set関数を推奨する。 templateconstexpr mint_base fact(mint_base x)noexcept { mint_base res(1); for (uint64_t i = 1; i <= (uint64_t)x; ++i) { res *= i; } return res; } //mint_baseの階乗計算 //0からxまでの階乗を返す //O(x)時間が必要 templatestd::vector> fact_set(mint_base x = mint_base(-1)) { mint_base res(1); std::vector> set((uint64_t)(x)+1); set[0] = 1; for (uint64_t i = 1; i <= (uint64_t)x; ++i) { res *= i; set[i] = res; } return res; } //mint_base型のstreamへの出力 template std::ostream& operator<<(std::ostream& os, mint_base i) { os << (uint64_t)i; return os; } //mint_base型のstreamからの入力 template std::istream& operator >> (std::istream& is, mint_base& i) { uint64_t tmp; is >> tmp; i = tmp; return is; } typedef mint_base<> mint; namespace mint_literal { constexpr mint operator""_mi(unsigned long long x)noexcept { return mint(x); } } using namespace mint_literal; int64_t A[300000]; mint mn[300000]; int main() { using std::endl; in.sync_with_stdio(false); out.sync_with_stdio(false); in.tie(nullptr); out.tie(nullptr); int64_t N; mint M; in >> N >> M; for (int i = 0; i < N; i++) { in >> A[i]; } std::sort(A, A + N); mint over = 0; mn[0] = 1; for (size_t i = 1; i < 300000; i++) { mn[i] = mn[i - 1] * M; } mint swapsum = 0; mint sum = 0; for (int i = N - 1; i >= 0; i--) { if (i != N - 1) { over = mint(N - i - 1) * mint(A[i + 1] - A[i]); } sum += (M - A[i]) * mn[N-1]; auto swap = mint(A[i]) * over * mn[N-2]; swap -= swapsum / M * mint(A[i]); swapsum += swap; sum += swap; } out << sum << endl; return 0; } #endif