网站开发获取用户微信号登录,网站开发电话话术,wordpress自定义页面编码,wordpress 赞助插件树的统计
金牌导航 树链剖分-1
题目大意
给出一棵树#xff0c;让你做若干操作#xff0c;操作如下#xff1a; 1.修改一个节点的值 2.查询两个节点之间路径的最大值 3.查询两个节点之间路径的和
输入样例
4
1 2
2 3
4 1
4 2 1 3
12
QMAX 3 4
QMAX 3 3
QMAX 3 2
QMAX 2…树的统计
金牌导航 树链剖分-1
题目大意
给出一棵树让你做若干操作操作如下 1.修改一个节点的值 2.查询两个节点之间路径的最大值 3.查询两个节点之间路径的和
输入样例
4
1 2
2 3
4 1
4 2 1 3
12
QMAX 3 4
QMAX 3 3
QMAX 3 2
QMAX 2 3
QSUM 3 4
QSUM 2 1
CHANGE 1 5
QMAX 3 4
CHANGE 3 6
QMAX 3 4
QMAX 2 4
QSUM 3 4输出样例
4
1
2
2
10
6
5
6
5
16数据范围
1⩽N⩽3×104,0⩽q⩽2×105,−3×104⩽si⩽3×1041\leqslant N\leqslant 3\times 10^4,0\leqslant q\leqslant 2\times10^5,-3\times 10^4\leqslant s_i\leqslant 3\times 10^41⩽N⩽3×104,0⩽q⩽2×105,−3×104⩽si⩽3×104
解题思路
树链剖分然后用线段树维护重链每个节点维护最大值和权值和
代码
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define N 30030
using namespace std;
int n, m, x, y, w, tot, ansmax, anssum;
int a[N], s[N4], v[N], fa[N], hs[N], han[N], dfn[N], dep[N], size[N], head[N], maxx[N4];
string str;
struct rec
{int to, next;
}e[N1];
void add(int x, int y)
{e[tot].to y;e[tot].next head[x];head[x] tot;
}
void dfs1(int x)//找重儿子
{size[x] 1;for (int i head[x]; i; i e[i].next)if (e[i].to ! fa[x]){fa[e[i].to] x;dep[e[i].to] dep[x] 1;dfs1(e[i].to);size[x] size[e[i].to];if (size[e[i].to] size[hs[x]]) hs[x] e[i].to;}return;
}
void dfs2(int x)
{dfn[x] w;v[w] x;if (hs[x]){han[hs[x]] han[x];//重祖先dfs2(hs[x]);}for (int i head[x]; i; i e[i].next)if (e[i].to ! fa[x] e[i].to ! hs[x]){han[e[i].to] e[i].to;dfs2(e[i].to);}
}
void up(int x)
{s[x] s[x * 2] s[x * 2 1];maxx[x] max(maxx[x * 2], maxx[x * 2 1]);return;
}
void build(int now, int l, int r)//线段树维护
{if (l r){maxx[now] s[now] a[v[l]];return;}int mid (l r) 1;build(now * 2, l, mid);build(now * 2 1, mid 1, r);up(now);return;
}
void change(int x, int y, int now, int l, int r)
{if (l r){maxx[now] s[now] y;return;}int mid (l r) 1;if (x mid) change(x, y, now * 2, l, mid);else change(x, y, now * 2 1, mid 1, r);up(now);return;
}
void ask(int now, int ql, int qr, int l, int r)
{if (l ql r qr){ansmax max(ansmax, maxx[now]);anssum s[now];return;}int mid (l r) 1;if (qr mid) {ask(now * 2, ql, qr, l, mid); return;}if (ql mid) {ask(now * 2 1, ql, qr, mid 1, r); return;}ask(now * 2, ql, mid, l, mid);ask(now * 2 1, mid 1, qr, mid 1, r);return;
}
void askk(int x, int y)//计算路径长度
{anssum 0;ansmax -N;while(han[x] ! han[y]){if (dep[han[x]] dep[han[y]]) swap(x, y);ask(1, dfn[han[x]], dfn[x], 1, n);x fa[han[x]];}if (dep[x] dep[y]) swap(x, y);ask(1, dfn[y], dfn[x], 1, n);return;
}
int main()
{scanf(%d, n);for (int i 1; i n; i){scanf(%d%d, x, y);add(x, y);add(y, x);}for (int i 1; i n; i)scanf(%d, a[i]);fa[1] 1;han[1] 1;dfs1(1);dfs2(1);build(1, 1, n);scanf(%d, m);while(m--){cinstr;scanf(%d%d, x, y);if (str CHANGE){change(dfn[x], y, 1, 1, n);}else{askk(x, y);if (str QSUM) printf(%d\n, anssum);else if (str QMAX) printf(%d\n, ansmax);}}return 0;
}
