Multiplication, DFS order

 

目录

路径最小值​

DFSsequence practice1

DFSsequence practice2

---

路径最小值

 

 

 

dfs,Equivalent to an initialization operation;

and there is aSTTable-like preprocessing operations

queryThe overall idea is of function,利用2Depth of nodes to keep looking up the nearest common ancestor.（前提是2nodes are at the same depth,This is reflected in the code,probably after the same depth,u就是v的祖先,也可能不是,Keep up）

// problem :  

#include <bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> PII;
#define pb push_back
const int LOGN = 18;
const int N = 201000;
int n, q;
int dep[N], par[N][LOGN + 1], val[N][LOGN + 1];
std::vector<pair<int, int>> e[N];

int query(int u, int v) {
   int ans = 1 << 30;
   if(dep[u] > dep[v]) swap(u, v);
   int d = dep[v] - dep[u];
   for (int j = LOGN; j >= 0; --j) if (d & (1 << j)) {
      ans = min(ans, val[v][j]);
      v = par[v][j];
   }
   if (u == v) return ans;
   for (int j = LOGN; j >= 0; --j) if (par[u][j] != par[v][j]) {
      ans = min(ans, min(val[u][j], val[v][j]));
      u = par[u][j];
      v = par[v][j];
   }
   ans = min(ans, min(val[u][0], val[v][0]));
   return ans;
}
void dfs(int u, int f) {
   dep[u] = dep[f] + 1;
   for (auto p : e[u]) {
      int v = p.first;
      if (v == f) continue;
      par[v][0] = u;
      val[v][0] = p.second;
      dfs(v, u);
   }
}
int main(){
   scanf("%d %d", &n, &q);
   for (int i = 1; i < n; ++i) {
      int u, v, w;
      scanf("%d %d %d", &u, &v, &w);
      e[u].push_back(make_pair(v, w));
      e[v].push_back(make_pair(u, w));
   }
   dfs(1, 0);
   for (int j = 1; j <= LOGN; ++j) {
      for (int u = 1; u <= n; ++u) {
         par[u][j] = par[par[u][j - 1]][j - 1];
         val[u][j] = min(val[u][j - 1], val[par[u][j - 1]][j - 1]);
      }
   }

   for (int i = 1; i <= q; ++i) {
      int u, v;
      scanf("%d %d", &u, &v);
      printf("%d\n", query(u, v));
   }

   return 0;
}

DFSsequence practice1

 

 

DFS序,   order a tree,The characteristic is that the sequence numbers of the subtrees are consecutive,（子树 相当于 involving interval issues）

c1  维护区间和   

c2 maintenance pointxpoint weights to the root and     （差分） 

Why do you think about the difference?？ 可以知道,点x's child is going to the root,Then it will passx,所以要加上x这个点的点权, So is the interval,and is a single point query,It is natural to think of differential tree arrays..

// problem :  DFS序
#include <bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> PII;
#define pb push_back
const int N = 201000;
int n, q, l[N], r[N], tot, a[N];
std::vector<int> e[N];

template<class T>
struct BIT{
    T c[N];
    int size;
    void init(int n){
        size = n;
        for (int i = 1; i <= n; ++i) c[i] = 0;
    }
    inline void modify(int x, T d){
        while(x <= size){
            c[x] += d;
            x += x & -x;
        }
    }
    inline T query(int x){
        T res = 0;
        while(x){
            res += c[x];
            x -= x & -x;
        }
        return res;
    }
};
BIT<ll> c1, c2;
void dfs(int u, int f) {
    l[u] = ++tot;
    for (auto v : e[u]) {
        if (v == f) continue;
        dfs(v, u);
    }
    r[u] = tot;
}
int main(){
    scanf("%d %d", &n, &q);
    for (int i = 1; i < n; ++i) {
        int u, v;
        scanf("%d %d", &u, &v);
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1, 0);
    c1.init(n);
    c2.init(n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        c1.modify(l[i], a[i]);
        c2.modify(l[i], a[i]);
        c2.modify(r[i] + 1, -a[i]);
    }

    for (int i = 1; i <= q; ++i) {
        int ty;
        scanf("%d", &ty);
        if (ty == 1) {
            int x, y;
            scanf("%d %d", &x, &y);
            int d = y - a[x];
            a[x] = y;
            c1.modify(l[x], d);
            c2.modify(l[x], d);
            c2.modify(r[x] + 1, -d);
        } else {
            int x;
            scanf("%d", &x);
            printf("%lld %lld\n", c1.query(r[x]) - c1.query(l[x] - 1), c2.query(l[x]));
        }
    }

    return 0;
}

 

DFSsequence practice2

 This question is no different from the previous one,The only change is that there is an additional root change operation,This is also one of the difficulties.

Once we change the root,那我们原先的DFSorder will be disrupted.The solution here is to not do a real rooting operation,and perform a logical root change.当我们查询xpoint weight and time of point subtree,通过x和root之间的关系,to simulate root replacement.

这里x和root之间有3种关系：

        1、x 就是 root          ---->  query(n)

        2、root是x的子孙     Overall minus x 的包含rootThe interval of the subinterval

        3、其他                   还是正常的query(r[x]) - query(l[x] - 1)

第1it's obvious,Demonstration without drawing.

第2种情况： 

 

 第3种情况：

 

// problem :  DFS序
#include <bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> PII;
#define pb push_back
const int N = 201000;
int n, q, l[N], r[N], tot, a[N];
std::vector<int> e[N];
vector<PII> son[N];
template<class T>
struct BIT{
    T c[N];
    int size;
    void init(int n){
        size = n;
        for (int i = 1; i <= n; ++i) c[i] = 0;
    }
    inline void modify(int x, T d){
        while(x <= size){
            c[x] += d;
            x += x & -x;
        }
    }
    inline T query(int x){
        T res = 0;
        while(x){
            res += c[x];
            x -= x & -x;
        }
        return res;
    }
};
BIT<ll> c1;
void dfs(int u, int f) {
    l[u] = ++tot;
    for (auto v : e[u]) {
        if (v == f) continue;
        dfs(v, u);
        son[u].push_back(make_pair(l[v], r[v]));
    }
    r[u] = tot;
}
int main(){
    scanf("%d %d", &n, &q);
    for (int i = 1; i < n; ++i) {
        int u, v;
        scanf("%d %d", &u, &v);
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1, 0);
    c1.init(n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        c1.modify(l[i], a[i]);
    }
    int root = 1;
    for (int i = 1; i <= q; ++i) {
        int ty;
        scanf("%d", &ty);
        if (ty == 1) {
            int x, y;
            scanf("%d %d", &x, &y);
            int d = y - a[x];
            a[x] = y;
            c1.modify(l[x], d);
        } else if (ty == 3){
            scanf("%d", &root);

        } else {
            int x;
            scanf("%d", &x);
            if (x == root) {
                printf("%lld\n", c1.query(n));
            } else if (l[x] < l[root] && r[x] >= r[root]) {
                auto seg = *prev(upper_bound(son[x].begin(), son[x].end(), 
                    PII {l[root], r[root]}));
                printf("%lld\n", c1.query(n) - (c1.query(seg.second) - c1.query(seg.first - 1)));
            } else {
                printf("%lld\n", c1.query(r[x]) - c1.query(l[x] - 1));
            }
        }
    }

    return 0;
}