低多边形网站,移动商城积分兑换官网,哈尔滨网站建设收费,有没有学做家具的网站题目背景 动态树 题目描述 给定#xff2e;个点以及每个点的权值#xff0c;要你处理接下来的#xff2d;个操作。操作有#xff14;种。操作从#xff10;到#xff13;编号。点从#xff11;到#xff2e;编号。 #xff10;#xff1a;后接两个整数#xff08;个点以及每个点的权值要你处理接下来的个操作。操作有种。操作从到编号。点从到编号。 后接两个整数代表询问从到的路径上的点的权值的和。保证到是联通的。 后接两个整数代表连接到若到已经联通则无需连接。 后接两个整数代表删除边不保证边存在。 后接两个整数代表将点上的权值变成。 输入输出格式 输入格式 第行两个整数分别为和代表点数和操作数。 第行到第行每行一个整数整数在内代表每个点的权值。 第行到第行每行三个整数分别代表操作类型和操作所需的量。 输出格式 对于每一个号操作你须输出到的路径上点权的和。 输入输出样例 输入样例#13 3
1
2
3
1 1 2
0 1 2
0 1 1 输出样例#13
1说明 数据范围 因为只是模板题吧。。在这里直接放上代码。。 关于LCT可以看论文QTREE解法的一些研究 1 #includecstdio2 #includecstring3 #includeiostream4 using namespace std;5 6 int read(){7 char ch;8 int re0;9 bool flag0;10 while((chgetchar())!-(ch0||ch9));11 ch-?flag1:rech-0;12 while((chgetchar())0ch9) rere*10ch-0;13 return flag?-re:re;14 }15 16 struct Splay{17 int ch[2],xr,fa;18 bool rev;19 };20 21 const int maxn300005;22 23 int n,m,top;24 int val[maxn],stk[maxn];25 Splay T[maxn];26 27 inline void push_up(int x){ T[x].xrT[T[x].ch[0]].xr^T[T[x].ch[1]].xr^val[x]; }28 29 inline bool isroot(int x){30 return T[T[x].fa].ch[0]!xT[T[x].fa].ch[1]!x;31 }32 33 inline void push_down(int x){34 if(T[x].rev){35 T[T[x].ch[0]].rev^1;36 T[T[x].ch[1]].rev^1;37 swap(T[x].ch[0],T[x].ch[1]);38 T[x].rev0;39 }40 }41 42 void rot(int x){43 int yT[x].fa,zT[y].fa,l,r;44 if(T[y].ch[0]x) l0;45 else l1;46 rl^1;47 T[x].faz;48 if(!isroot(y)) T[z].ch[T[z].ch[1]y]x;49 T[T[x].ch[r]].fay;50 T[y].ch[l]T[x].ch[r];51 T[y].fax;52 T[x].ch[r]y;53 push_up(y),push_up(x);54 }55 56 void splay(int x){57 top1; stk[top]x;58 for(int ix;!isroot(i);iT[i].fa) stk[top]T[i].fa;59 for(int itop;i;i--) push_down(stk[i]);60 while(!isroot(x)){61 int yT[x].fa,zT[y].fa;62 if(!isroot(y)){63 if((T[y].ch[0]x)^(T[z].ch[0]y)) rot(x);64 else rot(y);65 }66 rot(x);67 }68 }69 70 void acc(int x){71 int t0;72 while(x){73 splay(x);74 T[x].ch[1]t;75 push_up(x);76 tx; xT[x].fa;77 }78 }79 80 void make_root(int x){81 acc(x);82 splay(x);83 T[x].rev^1;84 }85 86 int find(int x){87 acc(x);88 splay(x);89 while(T[x].ch[0]) xT[x].ch[0];90 return x;91 }92 93 void split(int x,int y){94 make_root(x);95 acc(y);96 splay(y);97 }98 99 void cut(int x,int y){
100 split(x,y);
101 if(T[y].ch[0]x) T[y].ch[0]0,T[x].fa0;
102 }
103
104 void link(int x,int y){
105 make_root(x);
106 T[x].fay;
107 }
108
109 int main(){
110 // freopen(temp.in,r,stdin);
111 nread(),mread();
112 for(int i1;in;i){
113 val[i]read();
114 T[i].xrval[i];
115 }
116 int opt,x,y,xx,yy;
117 while(m--){
118 optread(),xread(),yread();
119 switch(opt){
120 case 0:{
121 split(x,y);
122 printf(%d\n,T[y].xr);
123 break;
124 }
125 case 1:{
126 xxfind(x),yyfind(y);
127 if(xx!yy) link(x,y);
128 break;
129 }
130 case 2:{
131 xxfind(x),yyfind(y);
132 if(xxyy) cut(x,y);
133 break;
134 }
135 case 3:{
136 acc(x);
137 splay(x);
138 val[x]y;
139 push_up(x);
140 break;
141 }
142 }
143 }
144 return 0;
145 } 转载于:https://www.cnblogs.com/ZYBGMZL/p/7376234.html
