首页 > 代码库 > bzoj 2631: tree 动态树+常数优化
bzoj 2631: tree 动态树+常数优化
2631: tree
Time Limit: 30 Sec Memory Limit: 128 MBSubmit: 1716 Solved: 576
[Submit][Status]
Description
一棵n个点的树，每个点的初始权值为1。对于这棵树有q个操作，每个操作为以下四种操作之一：
+ u v c：将u到v的路径上的点的权值都加上自然数c；
- u1 v1 u2 v2：将树中原有的边(u1,v1)删除，加入一条新边(u2,v2)，保证操作完之后仍然是一棵树；
* u v c：将u到v的路径上的点的权值都乘上自然数c；
/ u v：询问u到v的路径上的点的权值和，求出答案对于51061的余数。
Input
第一行两个整数n，q
接下来n-1行每行两个正整数u，v，描述这棵树
接下来q行，每行描述一个操作
接下来n-1行每行两个正整数u，v，描述这棵树
接下来q行，每行描述一个操作
Output
对于每个/对应的答案输出一行
Sample Input
3 2
1 2
2 3
* 1 3 4
/ 1 1
1 2
2 3
* 1 3 4
/ 1 1
Sample Output
4
HINT
数据规模和约定
10%的数据保证，1<=n，q<=2000
另外15%的数据保证，1<=n，q<=5*10^4，没有-操作，并且初始树为一条链
另外35%的数据保证，1<=n，q<=5*10^4，没有-操作
100%的数据保证，1<=n，q<=10^5，0<=c<=10^4
动态树编的还是不熟练，这道题的模数是刚刚爆int的(51061^2==2607225721>2147483647),如果用long long 又要TLE，所以必须用unsigned int.
这道题涉及到动态树的路径操作，具体用法是通过make_root()access()将一个路径上所有点集中到一个splay中。
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<ctime>#include<cmath>#include<algorithm>#include<set>#include<map>#include<vector>#include<string>#include<queue>using namespace std;#ifdef WIN32#define LL "%I64d"#else#define LL "%lld"#endif#define MAXN 110000#define MAXT MAXN*2#define MAXV MAXN*2#define MAXE MAXV*2#define INF 0x3f3f3f3f#define INFL 0x3f3f3f3f3f3f3f3fLL#define lch ch[now][0]#define rch ch[now][1]#define plus _plus#define MOD 51061//刚刚爆inttypedef unsigned int qword;inline int nextInt(){ char ch; int x=0; bool flag=false; do ch=(char)getchar(),flag=(ch==‘-‘)?true:flag; while(ch<‘0‘||ch>‘9‘); do x=x*10+ch-‘0‘; while (ch=(char)getchar(),ch<=‘9‘ && ch>=‘0‘); return x*(flag?-1:1);}int n,m;struct Edge{ int np; Edge *next;}E[MAXE],*V[MAXV];int tope=-1;int fa[MAXT];int depth[MAXT];inline void addedge(int x,int y){ E[++tope].np=y; E[tope].next=V[x]; V[x]=&E[tope];}void dfs(int now){ Edge *ne; for (ne=V[now];ne;ne=ne->next) { if (ne->np==fa[now])continue; fa[ne->np]=now; depth[ne->np]=depth[now]+1; dfs(ne->np); }}//------------------------Link Cut Tree------------------------int pnt[MAXT],ch[MAXT][2];qword sum[MAXT],val[MAXT];qword mult[MAXT],plus[MAXT];bool flip[MAXT];int stack[MAXT],tops=-1;int siz[MAXT];void init(){ int i; for (i=1;i<=n;i++) { pnt[i]=fa[i]; mult[i]=1; plus[i]=0; val[i]=sum[i]=1; flip[i]=false; siz[i]=1; }}inline bool is_root(int now)//是splay上的根{ return (!pnt[now]) || (ch[pnt[now]][0]!=now && ch[pnt[now]][1]!=now);}inline void up(int now){ sum[now]=(sum[lch]+sum[rch]+val[now])%MOD; siz[now]=(siz[lch]+siz[rch]+1)%MOD;}inline void reverse(int now){ if (!now)return; swap(ch[now][0],ch[now][1]); flip[now]^=1;}inline void make_multiply(int now,qword v)//对于一个splay的子树加标记下放{ mult[now]=mult[now]*v%MOD; plus[now]=plus[now]*v%MOD; sum[now]=sum[now]*v%MOD; val[now]=val[now]*v%MOD;}inline void make_plus(int now,qword v)//同make_multiply{ plus[now]=(plus[now]+v)%MOD; sum[now]=(sum[now]+v*siz[now])%MOD; val[now]=(val[now]+v)%MOD;}inline void down(int now){ if (flip[now]) { reverse(ch[now][0]); reverse(ch[now][1]); flip[now]=false; } if (mult[now]!=1) { make_multiply(ch[now][0],mult[now]); make_multiply(ch[now][1],mult[now]); mult[now]=1; } if (plus[now]) { make_plus(ch[now][0],plus[now]); make_plus(ch[now][1],plus[now]); plus[now]=0; }}inline void rotate(int now){ int p=pnt[now],anc=pnt[p]; if (is_root(now))throw 1; int dir=ch[p][0]==now; pnt[now]=anc; if (!is_root(p))/**/ ch[anc][ch[anc][1]==p]=now; ch[p][1-dir]=ch[now][dir]; pnt[ch[now][dir]]=p; pnt[p]=now; ch[now][dir]=p; up(p); up(now);}void splay(int now){ int x=now; while (!is_root(x)) { stack[++tops]=x; x=pnt[x]; } stack[++tops]=x; do{ down(stack[tops--]); }while (tops>=0); if (is_root(now))return ;//先下放标记,否则access中自动接在其他点上面 while (!is_root(now)) { int p=pnt[now],anc=pnt[p]; if (is_root(p))//注意判断的对象 { rotate(now); }else { if ((ch[anc][0]==p) == (ch[p][0]==now)) { rotate(p); rotate(now); }else { rotate(now); rotate(now); } } }}void access(int now)//需要记忆！{ int son=0; for (;now;now=pnt[son=now]) { splay(now); ch[now][1]=son; up(now); }// while (ch[now][0])// now=ch[now][0];// return now;}void make_root(int now){ access(now); splay(now); swap(ch[now][0],ch[now][1]); reverse(ch[now][0]); reverse(ch[now][1]); //reverse(now);//注意}void cut(int x,int y){ make_root(x); access(y); splay(x); ch[x][ch[x][1]==y]=0; pnt[y]=0; up(x); up(y);}void link(int x,int y){// access(y); splay(y); make_root(x); access(x); splay(x); pnt[x]=y; up(y);}void scan(int now){ if (!now)return ; down(now); scan(lch); printf("%d ",(int)val[now]); scan(rch);}int main(){ //freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout); int i; int x,y,z; int a,b,c,d; scanf("%d%d",&n,&m); for (i=1;i<n;i++) { x=nextInt();y=nextInt(); //scanf("%d%d",&x,&y); addedge(x,y); addedge(y,x); } scanf("\n"); dfs(1); init(); char opt; for (i=0;i<m;i++) { opt=(int)getchar(); //scanf("%c",&opt); if (opt==‘+‘) { x=nextInt();y=nextInt();z=nextInt(); //scanf("%d%d%d\n",&x,&y,&z); z%=MOD; make_root(x); access(y); splay(y); make_plus(y,z); }else if (opt==‘-‘) { a=nextInt();b=nextInt();c=nextInt();d=nextInt(); //scanf("%d%d%d%d\n",&a,&b,&c,&d); cut(a,b); link(c,d); }else if (opt==‘*‘) { x=nextInt();y=nextInt();z=nextInt(); //scanf("%d%d%d\n",&x,&y,&z); z%=MOD; make_root(x); access(y); splay(y); make_multiply(y,z); }else if (opt==‘/‘) { x=nextInt();y=nextInt(); //scanf("%d%d\n",&x,&y); make_root(x); access(y); splay(y); printf("%d\n",(int)sum[y]); } } return 0;}
bzoj 2631: tree 动态树+常数优化
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。