Advertisement
MinhNGUYEN2k4

Untitled

Sep 11th, 2021
892
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.77 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(){
  83.     queue<int> q;
  84.     for(int i=1; i<=n; i++){
  85.         if (g[i].size()==1 && i!=1) q.push(i), vst[i]=1;
  86.     }
  87.     while (q.size()){
  88.         int u = q.front();
  89.         q.pop();
  90.         for(auto v : g[u]){
  91.             if (d[v]<d[u]) f[v]+=f[u];
  92.             if (!vst[v]&&d[v]<d[u]){
  93.                 vst[v]=1;
  94.                 q.push(v);
  95.             }
  96.         }
  97.     }
  98. }
  99.  
  100. void dfs2(int u, int pre){
  101.     for(auto v : g[u]){
  102.         if (v!=pre){
  103.             f[v] += f[u];
  104.             dfs2(v,u);
  105.         }
  106.     }
  107. }
  108.  
  109. void proc()
  110. {
  111.     par[1][0] = 0;
  112.     dfs(1,1);
  113.     memset(f, 0, sizeof f);
  114.     for(int i=1; i<=m; i++){
  115.         int u, v, w;
  116.         cin >> u >> v >> w;
  117.         int z = lca(u,v);
  118.         f[u]+=w;
  119.         f[v]+=w;
  120.         f[z]-=w;
  121.         f[par[z][0]]-=w;
  122.     }
  123.     dfs1();
  124.     dfs2(1,1);
  125.     while (q--){
  126.         int u, v;
  127.         cin >> u >> v;
  128.         int z = lca(u,v);
  129.         //cout << u << ' ' << v << ' ' << z << endl;
  130.         cout << f[u]+f[v]-f[z]-f[par[z][0]] << endl;
  131.     }
  132. }
  133.  
  134. signed main()
  135. {
  136.     readfile();
  137.     proc();
  138.     return 0;
  139. }
  140.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement