网站开发进阶实训报告,廊坊安次区网站建设公司,沧州做网站推广,建设网站的要求吗Description 一棵树上有$n$个节点,编号分别为$1$到$n$,每个节点都有一个权值$w_i$. 有三种操作: $1.CHANGE\;u\;t$:把结点$u$的权值改为$t$; $2.QMAX\;u\;v$:询问从点$u$到点$v$的路径上的节点的最大权值; $3.QSUM\;u\;v$:询问从点$u$到点$v$的路径上的节点的权值和. $P.S.$ 从…Description 一棵树上有$n$个节点,编号分别为$1$到$n$,每个节点都有一个权值$w_i$. 有三种操作: $1.CHANGE\;u\;t$:把结点$u$的权值改为$t$; $2.QMAX\;u\;v$:询问从点$u$到点$v$的路径上的节点的最大权值; $3.QSUM\;u\;v$:询问从点$u$到点$v$的路径上的节点的权值和. $P.S.$ 从点$u$到点$v$的路径上的节点包括$u$和$v$本身. Input 第$1$行,$1$个整数$n$,表示节点的个数. 接下来$n-1$行,每行$2$个整数$u$和$v$,表示节点$u$和$v$之间有一条边相连. 接下来$1$行,每行$n$个整数,第$i$个整数$w_i$.表示节点$i$的权值. 接下来$1$行,$1$个整数$q$,表示操作的总数. 接下来$q$行,每行$1$个操作,以$CHANGE\;u\;t$或者$QMAX\;u\;v$或者$QSUM\;u\;v$的形式给出. Output 对于每个$QMAX$”或者”$QSUM$”的操作,每行输出$1$个整数表示要求输出的结果. Sample Input 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 Sample Output 4 1 2 2 10 6 5 6 5 16 HINT $1\;\leq\;n\;\leq\;30000,0\;\leq\;q\;\leq\;200000$. 中途操作中保证每个节点的权值$w_i\in[-30000,30000]$. Solution 树链剖分线段树. 不会树链剖分的,戳这-学习笔记-树链剖分 #includecmath
#includectime
#includequeue
#includestack
#includecstdio
#includevector
#includecstring
#includecstdlib
#includeiostream
#includealgorithm
#define N 30005
#define M 60005
using namespace std;
struct linetree{int l,r,s,m;
}lt[M];
struct graph{int nxt,to;
}e[M];
char c[10];
int g[N],w[N],ww[N],n,q,u,v,cnt;
int f[N],p[N],dep[N],siz[N],son[N],top[N];
/*top[u]:u所在的链的顶端节点,son[u]:u的重儿子*/
inline void addedge(int x,int y){e[cnt].nxtg[x];g[x]cnt;e[cnt].toy;
}
inline void dfs1(int u){int m0;siz[u]1;for(int ig[u];i;ie[i].nxt)if(!dep[e[i].to]){f[e[i].to]u;dep[e[i].to]dep[u]1;dfs1(e[i].to);siz[u]siz[e[i].to];if(siz[e[i].to]m){son[u]e[i].to;msiz[e[i].to];}}
}
inline void dfs2(int u,int tp){top[u]tp;p[u]cnt;ww[cnt]w[u];if(son[u]) dfs2(son[u],tp);for(int ig[u];i;ie[i].nxt){if(e[i].to!f[u]e[i].to!son[u])dfs2(e[i].to,e[i].to);}
}
inline void build(int u,int l,int r){lt[u].ll;lt[u].rr;if(lt[u].llt[u].r){int lefu1,rigu1|1;int mid(lt[u].llt[u].r)1;build(lef,l,mid);build(rig,mid1,r);lt[u].slt[lef].slt[rig].s;lt[u].mmax(lt[lef].m,lt[rig].m);}else lt[u].slt[u].mww[lt[u].l];
}
inline void cover(int u,int x,int k){if(lt[u].llt[u].r){int lefu1,rigu1|1;int mid(lt[u].llt[u].r)1;if(xmid) cover(lef,x,k);else cover(rig,x,k); lt[u].slt[lef].slt[rig].s;lt[u].mmax(lt[lef].m,lt[rig].m);}else lt[u].slt[u].mk;
}
inline int sum(int u,int l,int r){if(lt[u].lllt[u].rr)return lt[u].s;if(lt[u].llt[u].r){int lefu1,rigu1|1,ret0;int mid(lt[u].llt[u].r)1;if(lmid) retsum(lef,l,r);if(rmid) retsum(rig,l,r);return ret;}
}
inline int qsum(int x,int y){int ret0;while(top[x]!top[y]){if(dep[top[x]]dep[top[y]]){retsum(1,p[top[x]],p[x]);xf[top[x]];}else{retsum(1,p[top[y]],p[y]);yf[top[y]];}}if(p[x]p[y]){int tx;xy;yt;}retsum(1,p[x],p[y]);return ret;
}
inline int ask(int u,int l,int r){if(lt[u].lllt[u].rr)return lt[u].m;if(lt[u].llt[u].r){int lefu1,rigu1|1,ret-30000;int mid(lt[u].llt[u].r)1;if(lmid) retmax(ret,ask(lef,l,r));if(rmid) retmax(ret,ask(rig,l,r));return ret;}
}
inline int qmax(int x,int y){int ret-30000;while(top[x]!top[y]){if(dep[top[x]]dep[top[y]]){retmax(ret,ask(1,p[top[x]],p[x]));xf[top[x]];}else{retmax(ret,ask(1,p[top[y]],p[y]));yf[top[y]];}}if(p[x]p[y]){int tx;xy;yt;}retmax(ret,ask(1,p[x],p[y]));return ret;
}
inline void Aireen(){scanf(%d,n);for(int i1,x,y;in;i){scanf(%d%d,x,y);addedge(x,y);addedge(y,x);}for(int i1;in;i)scanf(%d,w[i]);dep[1]1;dfs1(1);cnt0;dfs2(1,1);build(1,1,n);scanf(%d,q);while(q--){scanf(%s%d%d,c,u,v);if(c[1]H) cover(1,p[u],v);else if(c[1]M) printf(%d\n,qmax(u,v));else printf(%d\n,qsum(u,v));}
}
int main(){freopen(count.in,r,stdin);freopen(count.out,w,stdout);Aireen();fclose(stdin);fclose(stdout);return 0;
} 转载于:https://www.cnblogs.com/AireenYe/p/6219169.html
