admin 管理员组

文章数量: 887053

L

L - 芜湖塔台请求起飞

题目大意

给出一棵大小为 n n n的树，有如下操作：

  • 更改一个节点的权值
  • 查询从x到y路径上的权值和
  • 查询从x到y路径上的最大权值

题解

如果是在一个序列中，上面的操作非常容易用线段树来完成，但是在树上并不能。

于是就要想一个办法使得树变成一个序列。

很显然，就是树链剖分。

利用倍增求LCA，然后分别就是从x到LCA与从y到LCA的答案。

修改操作就直接在线段树上完成。

时间复杂度

线段树上一次查询的复杂度是 O ( log ⁡ n ) O(\log n) O(logn)的，

因为重边是连在 d f n dfn dfn一起的，可以一起查询，于是查询的次数就取决于轻边的次数。

根据重边的性质，可以知道，向下每走过一条轻边，子树大小至少减半，

那么最多走过的轻边数量就是 l o g n log_n logn​。

所以总的时间复杂度是 O ( q × log ⁡ 2 n ) O(q\times \log^2 n) O(q×log2n)。

Tag

树链剖分

线段树

倍增LCA

code

//#pragma GCC optimize (2)
//#pragma G++ optimize (2)
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#define G getchar
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
#define mx(x) a[x].mx
#define s(x) a[x].s
using namespace std;int read()
{char ch;for(ch = G();(ch < '0' || ch > '9') && ch != '-';ch = G());int n = 0 , w;if (ch == '-'){w = -1;ch = G();} else w = 1;for(;'0' <= ch && ch <= '9';ch = G())n = (n<<1)+(n<<3)+ch-48;return n * w;
}const int N = 30005;
int dfn [N] , son[N] , tot , n , m , fa [16] [N] , x , y , dep [N];
int nxt [ N << 1] , lst [N] , to [N << 1] , si [N] , v [N] , top [N];
int opv , opl , opr , opt , pos;struct node
{int mx , s;
}a[N << 2];void dfs_1 (int x)
{si [x] = 1;for (int i = lst [x] ; i ; i = nxt [i]){if (to [i] ^ fa [0] [x]){fa [0][ to[i] ] = x;dfs_1(to[i]);si[x] += si[to[i]];if (si[to[i]] > si[son[x]]) son[x] = to[i];}}
}void dfs_2 (int x)
{dep[x] = dep[fa[0][x]] + 1;dfn [x] = ++ tot;if (son[x]){top[son[x]] = top[x];dfs_2(son[x]);}for (int i = lst [x] ; i ; i = nxt [i])if (dfn[to[i]] == 0){top[to[i]] = to[i];dfs_2(to[i]);}
}int lca (int x , int y)
{if (dep[x] < dep[y]) swap(x , y);for (int i = 15 ; i >= 0 ; i--)if (dep[fa[i][x]] >= dep[y]) x = fa[i][x];for (int i = 15 ; i >= 0 ; i--)if (fa[i][x] ^ fa[i][y]){x = fa[i][x];y = fa[i][y];}if (x ^ y) return fa[0][x];else return x;
}void ins (int x , int y)
{nxt[++tot] = lst[x];to[tot] = y;lst[x] = tot;
}void updata (int x)
{mx(x) = max(mx(ls(x)) , mx(rs(x)));s(x) = s(ls(x)) + s(rs(x));
}void work (int x , int l , int r)
{if (opl <= l && r <= opr){switch (opt){case 1:{mx(x) = s(x) = opv;break;}case 2:{opv = opv + s(x);break;}case 3:{opv = max(opv , mx(x));break;}}return;}int m = (l + r) >> 1;if (opl <= m) work(ls(x) , l , m);if (m < opr) work(rs(x) , m + 1 , r);updata(x);
}void calc (int x , int y)
{for (; dep[top[x]] > dep[y] ;){opl = dfn[top[x]];opr = dfn[x];work(1 , 1 , n);x = fa[0][top[x]];}opl = dfn[y];opr = dfn[x];work(1 , 1 , n);
}int main()
{freopen("l.in","r",stdin);//freopen("l.out","w",stdout);n = read();for (int i = 1; i < n; ++i){x = read();y = read();ins (x , y);ins (y , x);}dfs_1(1);for (int i =1 ; i < 16; i++)for (int j = 1 ; j <= n ; j++)fa[i][j] = fa[i - 1][fa[i - 1][j]];tot = 0;top[1] = 1;dfs_2(1);opt = 1;for (int i = 1 ; i <= n ; i++){opv = read();opl = opr = dfn[i];v[i] = opv;work(1 , 1 , n);}m = read();for (int i = 0; i < m; ++i){opt = read();x = read();y = read();pos = lca(x , y);if (opt == 1){opl = opr = dfn[x];opv = y;v[x] = y;work(1 , 1 , n);}else{if (opt == 2) opv = -v[pos]; else opv = v[pos];calc(x , pos);calc(y , pos);printf("%d\n", opv);}}return 0;
}

本文标签： L

版权声明：本文标题：L 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1688345984h208880.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。