本题解提供两种做法。

做法一

为了叙述方便,先引入 \(n\) 级母树的概念。
定义 \(1\) 级母树即为该子树被删去前,其所在的原来的完整的树。

666

如下图,以 \(5\) 为根的一级母树为以 \(3\) 为根的原来的子树。类似地,以 \(1\) 为根的原来的树即为以 \(3\) 为根的树的 \(1\) 级母树以及以 \(5\) 为根的 \(2\) 级母树。

可以发现,题目中有这样一个条件:\(v \le 1000\)。也就是说,这棵树的初始情况是一个类菊花图。菊花图有一个很重要的性质,就是其深度非常浅。在题目中所给的条件下,假如我们从某一点按照其父亲一路跳至根节点,最多只能跳 \(1000\) 次。

利用这一性质,我们考虑维护每一个点的子树和 \(siz_u\)。那么,每一棵树的权值和即为其当前根节点的权值和。

考虑操作 \(1\), 我们直接模拟删去子树和。从现在被删树根节点 \(v\) 的父亲至其 \(1\) 级母树的根节点的路径上的所有点的子树和显然都要减掉 \(siz_v\)。一路上跳即可。

对于操作 \(2\), 我们计算出前后的改变量,从当前点到子树根节点上的 \(siz_i\) 显然都要加上改变量。一路上跳即可。

对于操作 \(3\), 按照上文所说,上跳到当前树的根节点查询即可。

代码:

#include <bits/stdc++.h>
using namespace std;
#define N 100010
#define ll long long
const int INF = 1e9; 

template <class T>
inline void read(T& a){
	T x = 0, s = 1;
	char c = getchar();
	while(!isdigit(c)){ if(c == '-') s = -1; c = getchar(); }
	while(isdigit(c)){ x = x * 10 + (c ^ '0'); c = getchar(); }
	a = x * s;
	return ;
}

struct node{
  int u, v, next;
} t[N << 1]; 
int head[N];

int bian = 0;
inline void addedge(int u, int v){
  t[++bian] = (node){u, v, head[u]}, head[u] = bian;
  return ; 
}

int n, m; 
int a[N]; 

struct hehe{
  int u, v; 
} h[N]; 

int deth[N], siz[N], fa[N]; 

void dfs1(int u, int father){
  fa[u] = father; 
  siz[u] = a[u]; 
  deth[u] = deth[father] + 1; 
  for(int i = head[u]; i; i = t[i].next){
    int v = t[i].v; 
    if(v != father){
      dfs1(v, u); 
      siz[u] += siz[v]; 
    }
  }
  return ; 
}

map <int, int> del[N]; // 记录删边情况

signed main(){
  // freopen("hh.txt", "r", stdin); 
  read(n), read(m);
  for(int i = 1; i <= n; i++) read(a[i]); 
  for(int i = 1; i < n; i++){
    int x, y;
    read(x), read(y);
    addedge(x, y); 
    addedge(y, x); 
    h[i].u = x, h[i].v = y; 
  }

  dfs1(1, 0);
  del[1][0] = del[0][1] = 1; 

  while(m--){
    int opt, e, x, y; 
    read(opt); 
    if(opt == 1){
      read(e); 
      int u = h[e].u; 
      int v = h[e].v; 
      if(deth[u] > deth[v]) swap(u, v); 
      del[u][v] = del[v][u] = 1; 
      while(!del[u][fa[u]]){
        // printf("u: %d  siz: %d\n", u, siz[v]); 
        siz[u] -= siz[v]; 
        u = fa[u]; 
      }
      // printf("u: %d  v: %d\n", u, siz[v]); 
      siz[u] -= siz[v]; 
    }
    else if(opt == 2){
      read(x), read(y); 
      int d = y - a[x]; 
      a[x] = y;
      while(!del[x][fa[x]]){
        siz[x] += d; 
        x = fa[x]; 
      }
      siz[x] += d; 
       
    }
    else{
      read(x);
      while(!del[x][fa[x]]) x = fa[x]; 
      cout << siz[x] << endl; 
    }
  }

  return 0;
}

方法二

考虑在原方法上进行升级。

思考:如果没有 \(v \le 1000\) 这个性质,我们暴力上跳的时间复杂度就会退化为 \(O(QN)\)。这显然是不行的。

可以发现,原方法的操作都是区间操作,于是考虑用树链剖分加线段树解决。

对于找当前点所在树的根,考虑如下性质:

  • 根一定是当前点的父亲或者他自己。
  • 在一条链上,各个点的 \(dfn\) 序是连续的,且深度浅的点一定小于深度大的点。

利用上面两个性质,可以发现,我们将删边操作下放到点,标记深度较深的那个点。查询时,断点一定与当前上跳的点在同一条链上,因此查询下标最大的那个即可。(即用线段树记录最大值。)

除了上面这个操作,剩下的上跳操作直接以树链剖分的区间修改替代即可。

#include <bits/stdc++.h>
using namespace std;
#define N 100010
#define ll long long
const int INF = 1e9; 

template <class T>
inline void read(T& a){
	T x = 0, s = 1;
	char c = getchar();
	while(!isdigit(c)){ if(c == '-') s = -1; c = getchar(); }
	while(isdigit(c)){ x = x * 10 + (c ^ '0'); c = getchar(); }
	a = x * s;
	return ;
}

struct node{
  int u, v, next;
} t[N << 1]; 
int head[N];

int bian = 0;
inline void addedge(int u, int v){
  t[++bian] = (node){u, v, head[u]}, head[u] = bian;
  return ; 
}

int n, m; 
int a[N]; 

struct hehe{
  int u, v; 
} h[N]; 

int dfn[N], id = 0, rev[N];
int son[N], deth[N], top[N], siz[N], fa[N]; 
int w[N]; 

void dfs1(int u, int father){
  fa[u] = father; 
  siz[u] = 1;
  w[u] = a[u];  
  deth[u] = deth[father] + 1; 
  int maxn = -INF; 
  for(int i = head[u]; i; i = t[i].next){
    int v = t[i].v; 
    if(v != father){
      dfs1(v, u); 
      siz[u] += siz[v]; 
      w[u] += w[v]; 
      if(siz[v] > maxn){
        son[u] = v; 
        maxn = siz[v]; 
      }
    }
  }
  return ; 
}

void dfs2(int u, int tp){
  top[u] = tp; 
  dfn[u] = ++id; rev[id] = u; 
  if(!son[u]) return ; 
  dfs2(son[u], tp); 
  for(int i = head[u]; i; i = t[i].next){
    int v = t[i].v; 
    if(v != fa[u] && v != son[u])
      dfs2(v, v); 
  }
  return ; 
}

struct Segment_tree{
  struct node{
    int w; 
    bool del;  // 这个点上面的那条边是否被删除
    int id;  // 被删除的最靠右的那个点
    int add; 
  } t[N << 2]; 

  #define lson (o<<1)
  #define rson (o<<1|1)

  inline void pushup(int o){
    t[o].w = t[lson].w + t[rson].w;
    t[o].del = t[lson].del | t[rson].del; 
    t[o].id = max(t[lson].id, t[rson].id); 
    return ; 
  }

  inline void pushdown(int o, int l, int r){
    int mid = l + r >> 1;
    t[lson].add += t[o].add;
    t[rson].add += t[o].add; 

    t[lson].w += t[o].add * (mid - l + 1); 
    t[rson].w += t[o].add * (r - mid);

    t[o].add = 0; 
    return ; 
  }

  void build(int o, int l, int r){
    t[o].del = 0; 
    t[o].id = -1; 
    if(l == r){
      t[o].w = w[rev[l]]; 
      return ; 
    }
    int mid = l + r >> 1;
    build(lson, l, mid);
    build(rson, mid + 1, r);
    pushup(o);
    return ; 
  }

  int query_sum(int o, int l, int r, int in, int end){
    if(l > end || r < in) return 0; 
    if(l >= in && r <= end) return t[o].w; 
    int mid = l + r >> 1;
    pushdown(o, l, r); 
    return query_sum(lson, l, mid, in, end) + query_sum(rson, mid + 1, r, in, end); 
  }

  void update2(int o, int l, int r, int x){  // 表示要把某个点上面的边删去
    if(l > x || r < x) return ; 
    if(l == r && l == x){
      t[o].del = 1; 
      t[o].id = l; 
      return ; 
    }
    int mid = l + r >> 1;
    pushdown(o, l, r); 
    update2(lson, l, mid, x); 
    update2(rson, mid + 1, r, x); 
    pushup(o);
    return ; 
  }

  int query_id(int o, int l, int r, int in, int end){  // 最靠右的被删除的点的 id
    if(l > end || r < in) return -INF;
    if(l >= in && r <= end) return t[o].id; 
    int mid = l + r >> 1;
    pushdown(o, l, r); 
    return max(query_id(lson, l, mid, in, end), query_id(rson, mid + 1, r, in, end)); 
  }

  void update3(int o, int l, int r, int in, int end, int k){  // 区间加法
    if(l > end || r < in) return ; 
    if(l >= in && r <= end){
      t[o].add += k; 
      t[o].w += (r - l + 1) * k; 
      return ; 
    }
    pushdown(o, l, r); 
    int mid = l + r >> 1; 
    update3(lson, l, mid, in, end, k); update3(rson, mid + 1, r, in, end, k);
    pushup(o);
    return ; 
  }

} tree; 

int get_id(int x){   // 找断点,返回原始编号
  while(top[x]){
    int num = tree.query_id(1, 1, n, dfn[top[x]], dfn[x]); 
    if(num > 0) return rev[num]; 
    x = fa[top[x]]; 
  }
  int num = tree.query_id(1, 1, n, dfn[top[x]], dfn[x]); 
  if(num > 0) return rev[num]; 
  return 1; 
}

void change(int x, int y, int k){  // x, y 路径上的全部加 k
  while(top[x] != top[y]){
    if(deth[x] < deth[y]) swap(x, y); 
    tree.update3(1, 1, n, dfn[top[x]], dfn[x], k); 
    x = fa[top[x]]; 
  }
  if(deth[x] > deth[y]) swap(x, y); 
  tree.update3(1, 1, n, dfn[x], dfn[y], k); 
  return ; 
}


signed main(){
  // freopen("hh.txt", "r", stdin); 
  read(n), read(m);
  for(int i = 1; i <= n; i++) read(a[i]); 
  for(int i = 1; i < n; i++){
    int x, y;
    read(x), read(y);
    addedge(x, y); 
    addedge(y, x); 
    h[i].u = x, h[i].v = y; 
  }

  dfs1(1, 0);
  dfs2(1, 0); 
  tree.build(1, 1, n); 

  while(m--){
    int opt, e, x, y; 
    read(opt); 
    if(opt == 1){
      read(e); 
      int u = h[e].u; 
      int v = h[e].v; 
      if(deth[u] > deth[v]) swap(u, v); 
      tree.update2(1, 1, n, dfn[v]); 
      int id = get_id(u);
      int d = tree.query_sum(1, 1, n, dfn[v], dfn[v]); 
      change(id, u, -d);  // 路径上的全部减掉 w[v] 值
    }
    else if(opt == 2){
      read(x), read(y); 
      int d = y - a[x]; 
      a[x] = y;
      int id = get_id(x); 
      change(id, x, d);   // 区间加上差值
    }
    else{
      read(x);
      int id = get_id(x); 
      cout << tree.query_sum(1, 1, n, dfn[id], dfn[id]) << endl; 
    }
  }

  return 0;
}

原文地址:http://www.cnblogs.com/wondering-world/p/16876793.html

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长! 2. 分享目的仅供大家学习和交流,请务用于商业用途! 3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入! 4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解! 5. 如有链接无法下载、失效或广告,请联系管理员处理! 6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需! 7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员! 8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性