Advertisement
MinhNGUYEN2k4

Untitled

Sep 18th, 2021
729
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.50 KB | None | 0 0
  1. //Nguyen Huu Hoang Minh
  2. #include <bits/stdc++.h>
  3. #define sz(x) int(x.size())
  4. #define all(x) x.begin(),x.end()
  5. #define reset(x) memset(x, 0,sizeof(x))
  6. #define pb push_back
  7. #define mp make_pair
  8. #define fi first
  9. #define se second
  10. #define N 100005
  11. #define remain(x) if (x > MOD) x -= MOD
  12. #define ii pair<int, int>
  13. #define iii pair<ii, int>
  14. #define iiii pair< ii , ii >
  15. #define viiii vector< iiii >
  16. #define vi vector<int>
  17. #define vii vector< ii >
  18. #define bit(x, i) (((x) >> (i)) & 1)
  19. #define Task "test"
  20. #define int long long
  21.  
  22. using namespace std;
  23.  
  24. typedef long double ld;
  25. const int inf = 1e10;
  26. const int minf = -1e10;
  27.  
  28. int n,m,q;
  29. vector<int> g[N];
  30. int d[N], par[N][20], f[N];
  31. int ic[N];
  32.  
  33. void readfile()
  34. {
  35.     ios_base::sync_with_stdio(false);
  36.     cin.tie(0);cout.tie(0);
  37.     if (fopen(Task".inp","r"))
  38.     {
  39.         freopen(Task".inp","r",stdin);
  40.         //freopen(Task".out","w",stdout);
  41.     }
  42.     cin >> n >> m >> q;
  43.     for(int i=1; i<n; i++){
  44.         int u, v;
  45.         cin >> u >> v;
  46.         g[u].pb(v);
  47.         g[v].pb(u);
  48.     }
  49. }
  50.  
  51. void dfs(int u, int pre){
  52.     for(int i=1; i<20; i++){
  53.         par[u][i] = par[par[u][i-1]][i-1];
  54.     }
  55.     for(auto v : g[u]){
  56.         if (v!=pre){
  57.             d[v] = d[u]+1;
  58.             par[v][0] = u;
  59.             dfs(v,u);
  60.         }
  61.     }
  62. }
  63.  
  64. int lca(int u, int v){
  65.     if (d[u] < d[v]) swap(u,v);
  66.     int delta = d[u]-d[v];
  67.     for(int i=19; i>=0; i--){
  68.         if (bit(delta,i)) u = par[u][i];
  69.     }
  70.     if (u==v) return u;
  71.     for(int i=19; i>=0; i--){
  72.         if (par[u][i]!=par[v][i]){
  73.             u = par[u][i];
  74.             v = par[v][i];
  75.         }
  76.     }
  77.     return par[u][0];
  78. }
  79.  
  80. int vst[N];
  81.  
  82. void dfs1(int u, int pre){
  83.     for(auto v : g[u]){
  84.         if (v!=pre){
  85.             dfs1(v,u);
  86.             f[u] += f[v];
  87.         }
  88.     }
  89. }
  90.  
  91. void dfs2(int u, int pre){
  92.     for(auto v : g[u]){
  93.         if (v!=pre){
  94.             f[v] += f[u];
  95.             dfs2(v,u);
  96.         }
  97.     }
  98. }
  99.  
  100. void proc()
  101. {
  102.     par[1][0] = 0;
  103.     dfs(1,1);
  104.     memset(f, 0, sizeof f);
  105.     for(int i=1; i<=m; i++){
  106.         int u, v, w;
  107.         cin >> u >> v >> w;
  108.         int z = lca(u,v);
  109.         f[u]+=w;
  110.         f[v]+=w;
  111.         f[z]-=w;
  112.         f[par[z][0]]-=w;
  113.     }
  114.     dfs1(1,1);
  115.     dfs2(1,1);
  116.     f[0] = 0;
  117.     while (q--){
  118.         int u, v;
  119.         cin >> u >> v;
  120.         int z = lca(u,v);
  121.         cout << f[u]+f[v]-f[z]-f[par[z][0]] << '\n';
  122.     }
  123. }
  124.  
  125. signed main()
  126. {
  127.     readfile();
  128.     proc();
  129.     return 0;
  130. }
  131.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement