网站建设公司宣传词,wordpress站点搬家,wordpress等待响应,试玩网站开发http://www.zybbs.org/JudgeOnline/problem.php?id2243 题目大意#xff1a;给你一棵树#xff0c;节点有颜色#xff0c;要求可以查询某路径中连续颜色段的数目和修改某一段路径的颜色。 两次拉实之后查询和修改即可。 #include iostream
#include cstdio… http://www.zybbs.org/JudgeOnline/problem.php?id2243 题目大意给你一棵树节点有颜色要求可以查询某路径中连续颜色段的数目和修改某一段路径的颜色。 两次拉实之后查询和修改即可。 #include iostream
#include cstdio
#include cstring
#include cstdlib
#include queue
#define NIL LCT
#define MM 200001
#define MN 100001
using namespace std;queueint q;
int n,m,a,b,c,color[MN];
char s[10];
struct EDGE{int pnt;EDGE *pre;EDGE (){}EDGE(int _pnt,EDGE *_pre):pnt(_pnt),pre(_pre){}
}Edge[MM],*EPEdge,*edge[MM];inline void addedge(int a,int b){edge[a]new(EP)EDGE(b,edge[a]);edge[b]new(EP)EDGE(a,edge[b]);
}struct LinkCutTree{struct NODE{int c,lc,rc,mark,cnt;bool root;NODE *left,*right,*father;NODE (){}NODE(int _c,NODE *_left,NODE *_right,NODE *_father):c(_c),lc(_c),rc(_c),left(_left),right(_right),father(_father){mark0,cnt1,roottrue;}}LCT[MN],*NP,*node[MN];void init(){NPNIL;NIL-cNIL-lcNIL-rcNIL-mark0;NIL-leftNIL-rightNIL-fatherNIL;NIL-rootfalse;}void build(){q.push(1);node[1]new(NP)NODE(color[1],NIL,NIL,NIL);while(!q.empty()){int iq.front();q.pop();for(EDGE *jedge[i];j;jj-pre)if(node[j-pnt]!node[i]-father){node[j-pnt]new(NP)NODE(color[j-pnt],NIL,NIL,node[i]);q.push(j-pnt);}}}void renew(NODE *t,int key){if(t!NIL) t-ct-lct-rct-markkey,t-cnt1;}void pushdown(NODE *t){if(t-mark){renew(t-left,t-mark);renew(t-right,t-mark);t-mark0;}}void update(NODE *t){t-lct-rct-c;if(t-left!NIL) t-lct-left-lc;if(t-right!NIL) t-rct-right-rc;t-cntt-left-cntt-right-cnt1;if(t-ct-left-rc) t-cnt--;if(t-ct-right-lc) t-cnt--;}void zig(NODE *t){NODE *ft-father,*rt-right;pushdown(f);pushdown(t);t-fatherf-father;if(f-root) t-roottrue,f-rootfalse;else{if(f-father-leftf) f-father-leftt;else f-father-rightt;}t-rightf,f-fathert,f-leftr,r-fatherf;update(f);}void zag(NODE *t){NODE *ft-father,*lt-left;pushdown(f);pushdown(t);t-fatherf-father;if(f-root) t-roottrue,f-rootfalse;else{if(f-father-leftf) f-father-leftt;else f-father-rightt;}t-leftf,f-fathert,f-rightl,l-fatherf;update(f);}void splay(NODE *t){pushdown(t);while(!t-root){if(t-father-root){if(t-father-leftt) zig(t);else zag(t);}else{if(t-father-father-leftt-father){if(t-father-leftt) zig(t-father),zig(t);else zag(t),zig(t);}else{if(t-father-leftt) zig(t),zag(t);else zag(t-father),zag(t);}}}update(t);}void Expose(NODE *t){NODE *pt,*qNIL;while(p!NIL){splay(p);p-right-roottrue;p-rightq;p-right-rootfalse;update(p);qp;pp-father;}}void Modify(int a,int b,int c){Expose(node[a]);NODE *pnode[b],*qNIL;while(p!NIL){splay(p);if(p-fatherNIL){p-cc;renew(p-right,c);renew(q,c);}p-right-roottrue;p-rightq;p-right-rootfalse;update(p);qp;pp-father;}}void query(int a,int b){Expose(node[a]);NODE *pnode[b],*qNIL;while(p!NIL){splay(p);if(p-fatherNIL){int ansq-cntp-right-cnt1;if(p-cq-lc) ans--;if(p-cp-right-lc) ans--;printf(%d\n,ans);}p-right-roottrue;p-rightq;p-right-rootfalse;update(p);qp;pp-father;}}
}tree;int main(){scanf(%d%d,n,m);for(int i1;in;i) scanf(%d,color[i]);for(int i1;in;i){scanf(%d%d,a,b);addedge(a,b);}tree.init();tree.build();while(m--){scanf(%s,s);if(s[0]Q){scanf(%d%d,a,b);tree.query(a,b);}else{scanf(%d%d%d,a,b,c);tree.Modify(a,b,c);}}return 0;
}转载于:https://www.cnblogs.com/Delostik/archive/2011/08/11/2134544.html
