fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define fi first
  6. #define se second
  7. #define ll long long
  8. #define file(name)                  \
  9.     if(fopen(name".inp", "r"))      \
  10.         freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout);
  11.  
  12. template <int Mod>
  13. struct Modular {
  14. private :
  15.     int val;
  16.     static int inverse(int a, int b) {
  17.         a %= b;
  18.         assert(a);
  19.         if(a == 1) return 1;
  20.         return int(b - (long long) inverse(b, a) * (long long) b / a);
  21.     }
  22. public :
  23.     Modular(long long x = 0) : val(x % Mod) { if(val < 0) val += Mod; }
  24.  
  25.     friend bool operator == (const Modular &a, const Modular &b) { return a.val == b.val; }
  26.     friend bool operator != (const Modular &a, const Modular &b) { return a.val != b.val; }
  27.  
  28.     Modular& operator = (const long long &x) { val = x % Mod; if(val < 0) val += Mod; return *this; }
  29.     Modular& operator = (const Modular &x) { val = x.val; return *this; }
  30.  
  31.     friend istream & operator >> (istream &in, Modular &a) { long long x; in >> x; a = Modular(x); return in; }
  32.     friend ostream & operator << (ostream &out, const Modular &a) { return out << a.val; }
  33.  
  34.     explicit operator int() const { return val; }
  35.     explicit operator bool() const { return val > 0; }
  36.  
  37.     Modular inv() const {
  38.         Modular res;
  39.         res.val = inverse(val, Mod);
  40.         return res;
  41.     }
  42.  
  43.     Modular operator ++() { (*this) += 1; return *this; }
  44.     Modular operator --() { (*this) -= 1; return *this; }
  45.     Modular operator ++(int) { (*this) += 1; return *this - 1; }
  46.     Modular operator --(int) { (*this) -= 1; return *this + 1; }
  47.  
  48.     Modular operator + () const { return *this; }
  49.     Modular operator - () const {
  50.         Modular res;
  51.         res.val = (val ? Mod - val : 0);
  52.         return res;
  53.     }
  54.  
  55.     Modular& operator += (const Modular &a) {
  56.         val += a.val;
  57.         if(val >= Mod) val -= Mod;
  58.         return *this;
  59.     }
  60.     Modular& operator -= (const Modular &a) {
  61.         val -= a.val;
  62.         if(val < 0) val += Mod;
  63.         return *this;
  64.     }
  65.     Modular& operator *= (const Modular &a) {
  66.         val = 1LL * val * a.val % Mod;
  67.         return *this;
  68.     }
  69.     Modular& operator /= (const Modular &a) {
  70.         (*this) *= a.inv();
  71.         return *this;
  72.     }
  73.     friend Modular operator + (const Modular &a, const Modular &b) { return Modular(a) += b; }
  74.     friend Modular operator - (const Modular &a, const Modular &b) { return Modular(a) -= b; }
  75.     friend Modular operator * (const Modular &a, const Modular &b) { return Modular(a) *= b; }
  76.     friend Modular operator / (const Modular &a, const Modular &b) { return Modular(a) /= b; }
  77. };
  78.  
  79. // const int Mod = 998244353;
  80. // const int Mod = 1e9 + 9; // 1000000009
  81. const int Mod = 1e9 + 7; // 1000000007
  82.  
  83. using Modint = Modular <Mod>;
  84.  
  85. template <class T> T pow(T a, long long b) {
  86.     T ans = 1, mul = a;
  87.     for (; b > 0; b >>= 1) {
  88.         if(b & 1LL) ans *= mul;
  89.         mul *= mul;
  90.     }
  91.     return ans;
  92. }
  93.  
  94. const int MAX = 1e5 + 5;
  95.  
  96. int n, q, depth[MAX], anc[MAX][20], sz[MAX];
  97. Modint dist[MAX], dp[MAX], sum[MAX], dp_par[MAX], sum_par[MAX];
  98. vector <pair <int, int>> adj[MAX];
  99.  
  100. int time_in[MAX], time_out[MAX];
  101.  
  102. Modint sqr(Modint x) { return x * x; }
  103.  
  104. void dfs(int u, int p) {
  105.     static int run = 0;
  106.     time_in[u] = ++run;
  107.     depth[u] = depth[p] + 1;
  108.     anc[u][0] = p;
  109.     for (int i = 1; i < 20; ++i) {
  110.         anc[u][i] = anc[anc[u][i - 1]][i - 1];
  111.     }
  112.     sz[u] = 1;
  113.     for (pair <int, int> tmp : adj[u]) if(tmp.fi != p) {
  114.         int v, w; tie(v, w) = tmp;
  115.         dist[v] = dist[u] + w;
  116.         dfs(v, u);
  117.         sum[u] += sum[v] + Modint(1LL * w * sz[v] % Mod);
  118.         dp[u] += sqr(Modint(w)) * sz[v] + 2 * w * sum[v] + dp[v];
  119.         sz[u] += sz[v];
  120.     }
  121.     time_out[u] = run;
  122. }
  123.  
  124. int __lca(int u, int v) {
  125.     if(depth[u] < depth[v]) swap(u, v);
  126.     for (int i = 19; i >= 0; --i) {
  127.         if(depth[anc[u][i]] >= depth[v]) {
  128.             u = anc[u][i];
  129.         }
  130.     }
  131.     if(u == v) return u;
  132.     for (int i = 19; i >= 0; --i) {
  133.         if(anc[u][i] != anc[v][i]) {
  134.             u = anc[u][i];
  135.             v = anc[v][i];
  136.         }
  137.     }
  138.     return anc[u][0];
  139. }
  140.  
  141. bool is_par(int u, int v) {
  142.     return time_in[u] <= time_in[v] && time_in[v] <= time_out[u];
  143. }
  144.  
  145. Modint D(int u, int v) {
  146.     return dist[u] + dist[v] - 2 * dist[__lca(u, v)];
  147. }
  148.  
  149. void brute_forces() {
  150.     while(q--) {
  151.         int u, v; cin >> u >> v;
  152.         Modint ans = 0;
  153.         for (int i = 1; i <= n; ++i) {
  154.             int sign = (is_par(v, i) ? 1 : -1);
  155.             ans += sqr(D(u, i)) * sign;
  156.         }
  157.         cout << ans << '\n';
  158.     }
  159.     exit(0);
  160. }
  161.  
  162. void _dfs(int u, int p) {
  163.     for (pair <int, int> tmp : adj[u]) if(tmp.fi != p) {
  164.         int v, w; tie(v, w) = tmp;
  165.         sum_par[v] = sum_par[u] + sum[u] + 1LL * (n - 2 * sz[v]) * w - sum[v];
  166.         dp_par[v] = dp_par[u] + dp[u] -
  167.         (sqr(Modint(w)) * sz[v] + 2 * w * sum[v] + dp[v]) +
  168.         2 * (sum_par[u] + sum[u] - sum[v] - 1LL * sz[v] * w) * w + (n - sz[v]) * sqr(Modint(w));
  169.         _dfs(v, u);
  170.     }
  171. }
  172.  
  173. void you_make_it(void) {
  174.     cin >> n >> q;
  175.     for (int i = 1; i < n; ++i) {
  176.         int u, v, w; cin >> u >> v >> w;
  177.         adj[u].emplace_back(v, w);
  178.         adj[v].emplace_back(u, w);
  179.     }
  180.  
  181.     dfs(1, 0), _dfs(1, 0);
  182. //    if(n <= 3000) brute_forces();
  183. //    for (int i = 1; i <= n; ++i) cout << sz[i] << " "; cout << '\n';
  184. //    for (int i = 1; i <= n; ++i) cout << sum[i] << " "; cout << '\n';
  185. //    for (int i = 1; i <= n; ++i) cout << dp[i] << " "; cout << '\n';
  186. //    for (int i = 1; i <= n; ++i) cout << sum_par[i] << " "; cout << '\n';
  187. //    for (int i = 1; i <= n; ++i) cout << dp_par[i] << " "; cout << '\n';
  188.     while(q--) {
  189.         int u, v; cin >> u >> v;
  190.         int x = __lca(u, v);
  191.         Modint ans = 0, res = dist[u] + dist[v] - 2 * dist[x];
  192.         if(x == v) {
  193.             ans = dp[u] + dp_par[u];
  194.             ans -= 2 * (sqr(res) * (n - sz[v]) + 2 * res * sum_par[v] + dp_par[v]);
  195.         } else {
  196.             ans = sz[v] * sqr(res) + 2 * res * sum[v] + dp[v];
  197.             ans = ans * 2 - dp[u] - dp_par[u];
  198.         }
  199.         cout << ans << '\n';
  200.     }
  201. }
  202.  
  203. signed main() {
  204.  
  205. #ifdef LOCAL
  206.     freopen("TASK.inp", "r", stdin);
  207.     freopen("TASK.out", "w", stdout);
  208. #endif
  209.     file("tree");
  210.     auto start_time = chrono::steady_clock::now();
  211.  
  212.     cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
  213.  
  214.     you_make_it();
  215.  
  216.     auto end_time = chrono::steady_clock::now();
  217.  
  218.     cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;
  219.  
  220.     return (0 ^ 0);
  221. }
  222.  
  223. // Dream it. Wish it. Do it.
  224.  
Success #stdin #stdout #stderr 0.01s 10344KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Execution time : 0[ms]
https://ideone.com/ZO0Or2
language:
C++ (gcc 8.3)
created:
17 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!