题目描述
如题&＃xff0c;已知一棵包含N个结点的树&＃xff08;连通且无环&＃xff09;&＃xff0c;每个节点上包含一个数值&＃xff0c;需要支持以下操作&＃xff1a;
操作1&＃xff1a; 格式&＃xff1a; 1 x y z 表示将树从x到y结点最短路径上所有节点的值都加上z
操作2&＃xff1a; 格式&＃xff1a; 2 x y 表示求树从x到y结点最短路径上所有节点的值之和
操作3&＃xff1a; 格式&＃xff1a; 3 x z 表示将以x为根节点的子树内所有节点值都加上z
操作4&＃xff1a; 格式&＃xff1a; 4 x 表示求以x为根节点的子树内所有节点值之和
输入输出格式
输入格式&＃xff1a;
第一行包含4个正整数N、M、R、P&＃xff0c;分别表示树的结点个数、操作个数、根节点序号和取模数&＃xff08;即所有的输出结果均对此取模&＃xff09;。
接下来一行包含N个非负整数&＃xff0c;分别依次表示各个节点上初始的数值。
接下来N-1行每行包含两个整数x、y&＃xff0c;表示点x和点y之间连有一条边&＃xff08;保证无环且连通&＃xff09;
接下来M行每行包含若干个正整数&＃xff0c;每行表示一个操作&＃xff0c;格式如下&＃xff1a;
操作1&＃xff1a; 1 x y z
操作2&＃xff1a; 2 x y
操作3&＃xff1a; 3 x z
操作4&＃xff1a; 4 x
输出格式&＃xff1a;
输出包含若干行&＃xff0c;分别依次表示每个操作2或操作4所得的结果&＃xff08;对P取模&＃xff09;
输入输出样例
5 5 2 24
7 3 7 8 0
1 2
1 5
3 1
4 1
3 4 2
3 2 2
4 5
1 5 1 3
2 1 3
2
21
说明
时空限制&＃xff1a;1s&＃xff0c;128M
数据规模&＃xff1a;
对于30%的数据&＃xff1a; N≤10,M≤10 N \leq 10, M \leq 10 N≤10,M≤10
对于70%的数据&＃xff1a; N≤103,M≤103 N \leq {10}^3, M \leq {10}^3 N≤103,M≤103
对于100%的数据&＃xff1a; N≤105,M≤105 N \leq {10}^5, M \leq {10}^5 N≤105,M≤105
&＃xff08; 其实&＃xff0c;纯随机生成的树LCA&＃43;暴力是能过的&＃xff0c;可是&＃xff0c;你觉得可能是纯随机的么233 &＃xff09;
样例说明&＃xff1a;
树的结构如下&＃xff1a;
各个操作如下&＃xff1a;
故输出应依次为2、21(重要的事情说三遍&＃xff1a;记得取模)
解题思路&＃xff1a;
裸的树链剖分的模板。。。
推荐写法&＃xff1a;
#include
using namespace std;
#define re register int
#define ll long long
#define INF 0x3f3f3f3f
#define maxn 100009
#define maxm
inline ll read()
{ll x&＃61;0,f&＃61;1;char ch&＃61;getchar();while(ch<&＃39;0&＃39;||ch>&＃39;9&＃39;){if(ch&＃61;&＃61;&＃39;-&＃39;)f&＃61;-1;ch&＃61;getchar();}while(ch>&＃61;&＃39;0&＃39;&&ch<&＃61;&＃39;9&＃39;){x&＃61;(x<<1)&＃43;(x<<3)&＃43;(ll)(ch-&＃39;0&＃39;);ch&＃61;getchar();}return x*f;
}
int id[maxn],rk[maxn],top[maxn],son[maxn],size[maxn],depth[maxn],fa[maxn];
int head[maxn],val[maxn],sum[maxn<<2],add[maxn<<2];
int n,m,k,ans,tot,cnt,root,base;
struct edge
{int to,nxt;
}p[maxn<<1];
#define ls(x) x<<1
#define rs(x) x<<1|1
void add_edge(re x,re y)
{p[&＃43;&＃43;cnt]&＃61;{y,head[x]},head[x]&＃61;cnt;
}void dfs1(int u,int father)
{depth[u]&＃61;depth[father]&＃43;1,fa[u]&＃61;father,size[u]&＃61;1;for(int i&＃61;head[u];i;i&＃61;p[i].nxt){int v&＃61;p[i].to;if(v&＃61;&＃61;father) continue;dfs1(v,u);size[u]&＃43;&＃61;size[v];if(size[v]>size[son[u]])son[u]&＃61;v;}
}void dfs2(int u,int father)
{top[u]&＃61;father,id[u]&＃61;&＃43;&＃43;tot,rk[tot]&＃61;u;if(!son[u]) return ;dfs2(son[u],father);for(int i&＃61;head[u];i;i&＃61;p[i].nxt){int v&＃61;p[i].to;if(v!&＃61;son[u]&&v!&＃61;fa[u])dfs2(v,v); }
}int mod(int x)
{return x>&＃61;base?x%base:x;
}void push_up(int x)
{sum[x]&＃61;sum[ls(x)]&＃43;sum[rs(x)];sum[x]&＃61;mod(sum[x]);
}void built(int x,int l,int r)
{if(l&＃61;&＃61;r){sum[x]&＃61;val[rk[l]];return ;}int mid&＃61;(l&＃43;r)>>1;built(ls(x),l,mid);built(rs(x),mid&＃43;1,r);push_up(x);
}void pass(int x,int l,int r,int k)
{add[x]&＃43;&＃61;k,add[x]&＃61;mod(add[x]);sum[x]&＃43;&＃61;(r-l&＃43;1)*k,sum[x]&＃61;mod(sum[x]);
}void push_down(int x,int l,int r)
{if(!add[x]) return ;int mid&＃61;(l&＃43;r)>>1;pass(ls(x),l,mid,add[x]);pass(rs(x),mid&＃43;1,r,add[x]);add[x]&＃61;0;
}int Ask(int x,int l,int r,int nl,int nr)
{int res&＃61;0;if(nl<&＃61;l&&r<&＃61;nr)return sum[x];push_down(x,l,r);int mid&＃61;(l&＃43;r)>>1;if(nl<&＃61;mid)res&＃43;&＃61;Ask(ls(x),l,mid,nl,nr),res&＃61;mod(res);if(mid<nr)res&＃43;&＃61;Ask(rs(x),mid&＃43;1,r,nl,nr),res&＃61;mod(res);push_up(x);return res;
}void Add(int x,int l,int r,int nl,int nr,int k)
{if(nl<&＃61;l&&r<&＃61;nr){add[x]&＃43;&＃61;k,add[x]&＃61;mod(add[x]);sum[x]&＃43;&＃61;(r-l&＃43;1)*k,sum[x]&＃61;mod(sum[x]);return ;}push_down(x,l,r);int mid&＃61;(l&＃43;r)>>1;if(nl<&＃61;mid)Add(ls(x),l,mid,nl,nr,k);if(mid<nr)Add(rs(x),mid&＃43;1,r,nl,nr,k);push_up(x);
} void Work1(int x,int y,int z)
{int fx&＃61;top[x],fy&＃61;top[y];while(fx!&＃61;fy){if(depth[fx]>depth[fy])swap(x,y),swap(fx,fy);Add(1,1,tot,id[fy],id[y],z);y&＃61;fa[fy],fy&＃61;top[y];}if(id[x]>id[y])swap(x,y);Add(1,1,tot,id[x],id[y],z);
}int Work2(int x,int y)
{int res&＃61;0,fx&＃61;top[x],fy&＃61;top[y];while(fx!&＃61;fy){if(depth[fx]>depth[fy]) swap(x,y),swap(fx,fy);res&＃43;&＃61;Ask(1,1,tot,id[fy],id[y]),res&＃61;mod(res);y&＃61;fa[fy],fy&＃61;top[y];}if(id[x]>id[y]) swap(x,y);res&＃43;&＃61;Ask(1,1,tot,id[x],id[y]),res&＃61;mod(res);
}int main()
{
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);n&＃61;read(),m&＃61;read(),root&＃61;read(),base&＃61;read();for(re i&＃61;1;i<&＃61;n;i&＃43;&＃43;)val[i]&＃61;read();for(re i&＃61;1;i
}
#include
using namespace std;
#define re register int
#define ll long long
#define INF 0x3f3f3f3f
#define maxn 100009
#define maxm
#define ls(x) x<<1
#define rs(x) x<<1|1
inline ll read()
{ll x&＃61;0,f&＃61;1;char ch&＃61;getchar();while(ch<&＃39;0&＃39;||ch>&＃39;9&＃39;){if(ch&＃61;&＃61;&＃39;-&＃39;)f&＃61;-1;ch&＃61;getchar();}while(ch>&＃61;&＃39;0&＃39;&&ch<&＃61;&＃39;9&＃39;){x&＃61;(x<<1)&＃43;(x<<3)&＃43;(ll)(ch-&＃39;0&＃39;);ch&＃61;getchar();}return x*f;
}
ll base;
int n,m,k,ans,tot,cnt,root;
struct edge
{int to,nxt;
}p[maxn<<1];
int head[maxn],id[maxn],fa[maxn],depth[maxn],size[maxn],son[maxn],rk[maxn],top[maxn];
ll sum[maxn<<2],add[maxn<<2],val[maxn];void add_edge(int x,int y)
{p[&＃43;&＃43;cnt].to&＃61;y,p[cnt].nxt&＃61;head[x],head[x]&＃61;cnt;
}void dfs1(int u,int father)
{depth[u]&＃61;depth[father]&＃43;1,size[u]&＃61;1,fa[u]&＃61;father;for(int i&＃61;head[u];i;i&＃61;p[i].nxt){int v&＃61;p[i].to;if(v&＃61;&＃61;father) continue;dfs1(v,u); size[u]&＃43;&＃61;size[v];if(size[v]>size[son[u]])son[u]&＃61;v;}
}void dfs2(int u,int father)
{top[u]&＃61;father;id[u]&＃61;&＃43;&＃43;tot;rk[tot]&＃61;u;if(!son[u])return ;dfs2(son[u],father);for(int i&＃61;head[u];i;i&＃61;p[i].nxt){int v&＃61;p[i].to;if(v!&＃61;son[u]&&v!&＃61;fa[u])dfs2(v,v);}
}void push_up(int x)
{sum[x]&＃61;(sum[ls(x)]&＃43;sum[rs(x)])%base;
}void built(int x,int l,int r)
{if(l&＃61;&＃61;r){sum[x]&＃61;val[rk[l]];return ;}int mid&＃61;(l&＃43;r)>>1;built(ls(x),l,mid);built(rs(x),mid&＃43;1,r);push_up(x);
}void pass(int x,int l,int r,ll k)
{add[x]&＃43;&＃61;k,add[x]%&＃61;base;sum[x]&＃43;&＃61;(r-l&＃43;1)*k,sum[x]%&＃61;base;
}void push_down(int x,int l,int r)
{if(!add[x]) return ;int mid&＃61;(l&＃43;r)>>1;pass(ls(x),l,mid,add[x]);pass(rs(x),mid&＃43;1,r,add[x]);add[x]&＃61;0;
}ll Query(int x,int l,int r,int nl,int nr)
{ll res&＃61;0;if(nl<&＃61;l&&r<&＃61;nr)return sum[x];push_down(x,l,r);int mid&＃61;(l&＃43;r)>>1;if(nl<&＃61;mid)res&＃43;&＃61;Query(ls(x),l,mid,nl,nr),res%&＃61;base;if(mid<nr)res&＃43;&＃61;Query(rs(x),mid&＃43;1,r,nl,nr),res%&＃61;base;push_up(x);return res%base;
}void Add(int x,int l,int r,int nl,int nr,ll k)
{if(nl<&＃61;l&&r<&＃61;nr){add[x]&＃43;&＃61;k,add[x]%&＃61;base;sum[x]&＃43;&＃61;(r-l&＃43;1)*k,sum[x]%&＃61;base;return ;}push_down(x,l,r);int mid&＃61;(l&＃43;r)>>1;if(nl<&＃61;mid)Add(ls(x),l,mid,nl,nr,k);if(mid<nr)Add(rs(x),mid&＃43;1,r,nl,nr,k);push_up(x);
}void Work1(int x,int y,ll z)
{int fx&＃61;top[x],fy&＃61;top[y];while(fx!&＃61;fy){if(depth[fx]>&＃61;depth[fy]){Add(1,1,tot,id[fx],id[x],z);x&＃61;fa[fx],fx&＃61;top[x];}else{Add(1,1,tot,id[fy],id[y],z);y&＃61;fa[fy],fy&＃61;top[y];}}if(id[x]<&＃61;id[y])Add(1,1,tot,id[x],id[y],z);elseAdd(1,1,tot,id[y],id[x],z);
}ll Work2(int x,int y)
{ll ans&＃61;0;int fx&＃61;top[x],fy&＃61;top[y];while(fx!&＃61;fy){if(depth[fx]>&＃61;depth[fy]){ans&＃43;&＃61;Query(1,1,tot,id[fx],id[x]);x&＃61;fa[fx];fx&＃61;top[x];}else{ans&＃43;&＃61;Query(1,1,tot,id[fy],id[y]);y&＃61;fa[fy];fy&＃61;top[y];}}if(id[x]<&＃61;id[y])ans&＃43;&＃61;Query(1,1,tot,id[x],id[y]),ans%&＃61;base;elseans&＃43;&＃61;Query(1,1,tot,id[y],id[x]),ans%&＃61;base;return ans%base;
}void Work3(int x,int y)
{Add(1,1,tot,id[x],id[x]&＃43;size[x]-1,y);
}ll Work4(int x)
{ll res&＃61;Query(1,1,tot,id[x],id[x]&＃43;size[x]-1);return res%base;
}int main()
{freopen("1.in","r",stdin);freopen("1.out","w",stdout);n&＃61;read(),m&＃61;read(),root&＃61;read(),base&＃61;read();for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)val[i]&＃61;read()%base;for(int i&＃61;1;i
}
京公网安备 11010802041100号