题目大意:
维护一棵树,每条边有边权,支持下列操作:
1.修改某条边的边权
2.将某条路经上的边权取反
3.询问某条路经上的和
4.询问某条路经上的最大值
5.询问某条路经上的最小值
--by BZOJ;
http://www.lydsy.com/JudgeOnline/problem.php?id=2157
有关树链剖分的详解,见:树链剖分
链剖模板,代码长了点,主要是线段树部分操作太多,注意可以把边权搞到点上;
代码如下:
1 #include<cstdio> 2 #define INF 0x3fffffff 3 using namespace std; 4 struct ss{ 5 int to,next,dis; 6 }x[40001]; 7 int first[20001],num; 8 int size[20001];//子树和// 9 int hway[20001];//重边// 10 int rank[20001];//点在line_tree中的位置// 11 int rankl[20001];//边所对点在line_tree中的位置// 12 int dis[20001];//点权 // 13 int top[20001];//重链顶 // 14 int dep[20001];//深度 // 15 int fa[20001];//父亲// 16 int a[20001];//line_tree的原line序列// 17 int ltre[100005]; 18 int max[100005]; 19 int min[100005]; 20 int lz[100005]; 21 int n,m,L,R,X,W; 22 void swap(int&,int&); 23 void build(int ,int ,int ); 24 void dfs_1(int ); 25 void dfs_2(int ,int ); 26 void up(int ); 27 void down(int ,int ,int ); 28 void builtre(int ,int ,int ); 29 void work(int ); 30 int wor_(int ,int ); 31 void chan1(int ,int ,int ); 32 void chan2(int ,int ,int ); 33 int sum(int ,int ,int ); 34 int Max(int ,int ,int ); 35 int Min(int ,int ,int ); 36 int main() 37 { 38 int i,j,k,l; 39 char s[50]; 40 scanf("%d",&n); 41 for(i=0;i<=n-1;i++) 42 hway[i]=i; 43 for(i=1;i<=n-1;i++){ 44 scanf("%d%d%d",&j,&k,&l); 45 build(j,k,l); 46 build(k,j,l); 47 } 48 dep[0]=1; 49 dfs_1(0); 50 num=0; 51 dfs_2(0,0); 52 num=0; 53 builtre(1,n,1); 54 scanf("%d",&m); 55 for(i=1;i<=m;i++){ 56 scanf("%s",s); 57 scanf("%d%d",&L,&R); 58 if(s[1]!='