北京公司网站开发,阜阳建设大厦网站,上海 网站建设 外包it,如何软件开发题目描述 一棵树上有n个节点#xff0c;编号分别为1到n#xff0c;每个节点都有一个权值w。 我们将以下面的形式来要求你对这棵树完成一些操作#xff1a; I. CHANGE u t : 把结点u的权值改为t II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值 III. QSUM u v: 询问从… 题目描述 一棵树上有n个节点编号分别为1到n每个节点都有一个权值w。 我们将以下面的形式来要求你对这棵树完成一些操作 I. CHANGE u t : 把结点u的权值改为t II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值 III. QSUM u v: 询问从点u到点v的路径上的节点的权值和 注意从点u到点v的路径上的节点包括u和v本身 输入输出格式 输入格式 输入文件的第一行为一个整数n表示节点的个数。 接下来n – 1行每行2个整数a和b表示节点a和节点b之间有一条边相连。 接下来一行n个整数第i个整数wi表示节点i的权值。 接下来1行为一个整数q表示操作的总数。 接下来q行每行一个操作以“CHANGE u t”或者“QMAX u v”或者“QSUM u v”的形式给出。 输出格式 对于每个“QMAX”或者“QSUM”的操作每行输出一个整数表示要求输出的结果。 输入输出样例 输入样例#1 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 输出样例#1 4 1 2 2 10 6 5 6 5 16 说明 对于100的数据保证1n300000q200000中途操作中保证每个节点的权值w在-30000到30000之间。 树链剖分模板。。。 code //By Menteur_Hxy
#includecstdio
#includeiostream
#includealgorithm
#includecstring
#includevector
#includecmath
#define ll long long
#define f(a,b,c) for(int ab;ac;a)
using namespace std;inline ll rd() {ll x0,fla1; char c ;while(c9 || c0) {if(c-) fla-fla; cgetchar();}while(c9 c0) xx*10c-0,cgetchar();return x*fla;
}inline void out(ll x){int a[25],wei0;if(x0) putchar(-),x-x;for(;x;x/10) a[wei]x%10;if(wei0){ puts(0); return;}for(int jwei;j1;--j) putchar(0a[j]);putchar(\n);
}const int MAX300100;//直接开了十倍qwq
const int INF0x3f3f3f3f;
int n,cnt,N;int head[MAX],W[MAX],size[MAX],h[MAX],fa[MAX],son[MAX];
//W 点权 size 树的大小 h 深度 fa 父亲 son 重儿子 int num[MAX],top[MAX],tree[MAX],maxn[MAX],sumn[MAX];
//num 在线段树编号 top 链最上面的点 tree 线段树编号对应的点 struct edges{int next,to;
}edge[MAX]; void add(int a,int b) {edge[cnt](edges) {head[a],b}; head[a]cnt;edge[cnt](edges) {head[b],a}; head[b]cnt;
}void dfs1(int u,int pre,int dep) {size[u]1; h[u]dep; fa[u]pre;//initint mason0;for(int ihead[u];i;iedge[i].next) if(edge[i].to!pre) {int vedge[i].to;dfs1(v,u,dep1);size[u]size[v];if(size[v]mason) {masonsize[v];son[u]v;}}
}void dfs2(int u,int pre) {if(son[pre]!u) top[u]u;else top[u]top[pre];num[u]N;if(son[u]) dfs2(son[u],u);for(int ihead[u];i;iedge[i].next)if(edge[i].to!pre edge[i].to !son[u])dfs2(edge[i].to,u);
}void build_sum(int cur,int l,int r) {if(lr) {sumn[cur]W[tree[l]];return ;}int mid(lr)1;build_sum(cur1,l,mid);build_sum(cur1|1,mid1,r);sumn[cur]sumn[cur1]sumn[cur1|1];//update_sum
}void build_max(int cur,int l,int r) {if(lr) {maxn[cur]W[tree[l]];return ;}int mid(lr)1;build_max(cur1,l,mid);build_max(cur1|1,mid1,r);maxn[cur]max(maxn[cur1],maxn[cur1|1]);//update_max
}void po_ch_sum(int cur,int l,int r,int x,int v) {//point_change_sumif(lr) {sumn[cur]v;return ;}int mid(lr)1;if(xmid) po_ch_sum(cur1,l,mid,x,v);else po_ch_sum(cur1|1,mid1,r,x,v);sumn[cur]sumn[cur1]sumn[cur1|1];//update_sum
}void po_ch_max(int cur,int l,int r,int x,int v) {//point_change_maxif(lr) {maxn[cur]v;return ;}int mid(lr)1;if(xmid) po_ch_max(cur1,l,mid,x,v);else po_ch_max(cur1|1,mid1,r,x,v);maxn[cur]max(maxn[cur1],maxn[cur1|1]);
}int query_sum(int cur,int l,int r,int L,int R) {if(LlrR) return sumn[cur];int mid(lr)1,ans0;if(Lmid) ansquery_sum(cur1,l,mid,L,R);if(Rmid) ansquery_sum(cur1|1,mid1,r,L,R);return ans;
}int query_max(int cur,int l,int r,int L,int R) {if(LlrR) return maxn[cur];int mid(lr)1,ans-INF;if(Lmid) ansmax(ans,query_max(cur1,l,mid,L,R));if(Rmid) ansmax(ans,query_max(cur1|1,mid1,r,L,R));return ans;
}void INIT() {dfs1(1,0,1);// size h fa sondfs2(1,0);//top numf(i,1,n) tree[num[i]]i;//tree//建树 build_sum(1,1,N);build_max(1,1,N);
}void solve() {int qrd(),a,b,ans0,f1,f2;char opt[6];f(i,1,q) {scanf(%s,opt);ard(),brd(),ans0;if(opt[0]C) {//HCANGEpo_ch_sum(1,1,N,num[a],b);po_ch_max(1,1,N,num[a],b);}else {f1top[a],f2top[b];if(opt[1]M) ans-INF;while(f1!f2) {if(h[f1]h[f2]) {swap(a,b);swap(f1,f2);}if(opt[1]S) ansquery_sum(1,1,N,num[f1],num[a]);else ansmax(ans,query_max(1,1,N,num[f1],num[a]));afa[f1];f1top[a];}if(num[a]num[b]) swap(a,b);if(opt[1]S) ansquery_sum(1,1,N,num[a],num[b]);else ansmax(ans,query_max(1,1,N,num[a],num[b]));out(ans);}}
}int main() {nrd();f(i,1,n-1) add(rd(),rd());f(i,1,n) W[i]rd();INIT();solve();return 0;
} 转载于:https://www.cnblogs.com/Menteur-Hxy/p/9247981.html
