做素材网站存储,网站建设通用代码,网站开发常用图标,wordpress美金原题链接 对于以u为根的子树,后代节点的dfn显然比他的dfn大,我们可以记录一下回溯到u的dfn,显然这两个dfn构成了一个连续区间,代表u及u的子树 剩下的就和树剖一样了 1 #includecstdio2 #includealgorithm3 #includecstring4 #define N 1000105 typedef…原题链接 对于以u为根的子树,后代节点的dfn显然比他的dfn大,我们可以记录一下回溯到u的dfn,显然这两个dfn构成了一个连续区间,代表u及u的子树 剩下的就和树剖一样了 1 #includecstdio2 #includealgorithm3 #includecstring4 #define N 1000105 typedef long long ll;6 using namespace std;7 int ecnt,head[N],son[N],fa[N],sz[N],n,m,r,deep[N],pos[N],indx[N],tot,op,back[N],top[N];8 ll val[N],P;9 struct adj10 {11 int nxt,v;12 }e[2*N];13 struct node14 {15 int l,r;16 ll sum,lz;17 }t[4*N];18 void add(int u,int v)19 {20 e[ecnt].vv;21 e[ecnt].nxthead[u];22 head[u]ecnt;23 e[ecnt].vu;24 e[ecnt].nxthead[v];25 head[v]ecnt;26 }27 void dfs1(int x,int father,int dep)28 {29 deep[x]dep,fa[x]father,sz[x]1;30 for (int ihead[x];i;ie[i].nxt)31 {32 int ve[i].v;33 if (fa[x]v) continue;34 dfs1(v,x,dep1);35 sz[x]sz[v];36 if (sz[v]sz[son[x]]) son[x]v;37 }38 }39 void dfs2(int x,int TOP)40 {41 top[x]TOP;42 pos[x]tot;43 indx[tot]x;44 if (son[x]) dfs2(son[x],TOP);45 for (int ihead[x];i;ie[i].nxt)46 {47 int ve[i].v;48 if (vfa[x] || vson[x]) continue;49 dfs2(v,v);50 }51 back[x]tot;52 }53 void pushdown(int p)54 {55 if (t[p].lt[p].r || !t[p].lz) return;56 int wt[p].lz;57 t[p1].sum(t[p1].sumw*(t[p1].r-t[p].l1)%P)%P;58 t[p1|1].sum(t[p1|1].sumw*(t[p1|1].r-t[p1|1].l1)%P)%P;59 t[p1].lzw;60 t[p1].lz%P;61 t[p1|1].lzw;62 t[p1|1].lz%P;63 t[p].lz0;64 }65 void pushup(int p)66 {67 t[p].sum(t[p1].sumt[p1|1].sum)%P;68 }69 void build(int p,int l,int r)70 {71 t[p].ll,t[p].rr,t[p].lz0;72 if (l!r)73 {74 int midlr1;75 build(p1,l,mid);76 build(p1|1,mid1,r);77 pushup(p);78 }79 else80 t[p].sumval[indx[l]]%P;81 }82 void modify(int p,int l,int r,int w)83 {84 if (t[p].ll t[p].rr)85 {87 t[p].sumw*(t[p].r-t[p].l1);88 t[p].lzw;89 return ;90 }91 pushdown(p);92 int midt[p].lt[p].r1;93 if (rmid) modify(p1,l,r,w);94 else if (lmid) modify(p1|1,l,r,w);95 else modify(p1,l,mid,w),modify(p1|1,mid1,r,w);96 pushup(p);97 }98 ll query(int p,int l,int r)99 {
100 if (t[p].ll t[p].rr)
101 return t[p].sum%P;
102 int midt[p].lt[p].r1;
103 pushdown(p);
104 if (rmid) return query(p1,l,r)%P;
105 if (lmid) return query(p1|1,l,r)%P;
106 return (query(p1,l,mid)query(p1|1,mid1,r))%P;
107 }
108 void pathInc(int u,int v,int w)
109 {
110 while (top[u]!top[v])
111 {
112 if (deep[top[u]]deep[top[v]]) swap(u,v);
113 modify(1,pos[top[u]],pos[u],w);
114 ufa[top[u]];
115 }
116 if (deep[u]deep[v]) swap(u,v);
117 modify(1,pos[u],pos[v],w);
118 }
119 ll pathQuery(int u,int v)
120 {
121 ll ret0;
122 while (top[u]!top[v])
123 {
124 if (deep[top[u]]deep[top[v]]) swap(u,v);
125 ret(retquery(1,pos[top[u]],pos[u]))%P;
126 ufa[top[u]];
127 }
128 if (deep[u]deep[v]) swap(u,v);
129 return (retquery(1,pos[u],pos[v]))%P;
130 }
131 int main()
132 {
133 scanf(%d%d%d%lld,n,m,r,P);
134 for (int i1;in;i)
135 scanf(%lld,val[i]);
136 for (int i1,u,v;in;i)
137 scanf(%d%d,u,v),add(u,v);
138 dfs1(r,0,0);
139 dfs2(r,r);
140 build(1,1,n);
141 for (int i1,x,y,z;im;i)
142 {
143 scanf(%d,op);
144 if (op1)
145 scanf(%d%d%d,x,y,z),pathInc(x,y,z);
146 else if (op2)
147 scanf(%d%d,x,y),printf(%lld\n,pathQuery(x,y));
148 else if (op3)
149 scanf(%d%d,x,z),modify(1,pos[x],back[x],z);
150 else scanf(%d,x),printf(%lld\n,query(1,pos[x],back[x]));
151 }
152 return 0;
153 } 转载于:https://www.cnblogs.com/mrsheep/p/7892142.html
