PoPoQQQ 再一次orz…没看得特别明白的可以回来看看蒟蒻的补充口胡
我这里提一下关于splaysplaysplay维护的子树信息…
在原树上考虑,对于每一个点iii都有这样一个信息xi=ki∗xfa[i]+bix_i=k_i*x_{fa[i]}+b_ixi=ki∗xfa[i]+bi.
特别的,对于根节点rrr,设它的父亲为sf(special father)sf(special\ father)sf(special father),有xr=kr∗xsf+brx_r=k_r*x_{sf}+b_rxr=kr∗xsf+br.
那么我们要维护的就是对于这个联通块中的每一个点iii, xi=k′∗xsf+b′x_i=k'*x_{sf}+b'xi=k′∗xsf+b′的(k′,b′)(k',b')(k′,b′), 如果知道了每个点的这个信息, 那么就可以得到xsf=k′∗xsf+b′x_{sf}=k'*x_{sf}+b'xsf=k′∗xsf+b′,就能解出xsfx_{sf}xsf.进而解出所有的xix_ixi.回到LCTLCTLCT上,我们要求一个点iii的(k′,b′)(k',b')(k′,b′),首先access(i)access(i)access(i).那么从根到iii这条路径就成了一棵splaysplaysplay.因为一个点在splaysplaysplay中前驱是自己在原树上的父亲,自己是后继在原树上的父亲,那么我们定义一个结构体(k,b)(k,b)(k,b)用来表示线性关系.因为根节点(深度最小)肯定是splaysplaysplay中最左边的节点(一直往左儿子走),没有前驱,那么它的(k,b)(k,b)(k,b)值就是本身的xr=kr∗xsf+brx_r=k_r*x_{sf}+b_rxr=kr∗xsf+br中的(kr,br)(k_r,b_r)(kr,br).那么我们在splaysplaysplay的每个节点上维护一个线性关系(k,b)(k,b)(k,b),表示这个点xi=k∗xsf+bix_i=k*x_{sf}+b_ixi=k∗xsf+bi.
-
如何在splaysplaysplay上维护呢?我们定义一个运算来合并两个线性关系.比如有两个式子①和②.我们定义①*②表示把①合并到②上.也就是这样① y=k1x+b1② z=k2y+b2①\ y=k_1x+b_1\\②\ z=k_2y+b_2① y=k1x+b1② z=k2y+b2合并之后就是z=k2(k1x+b1)+b2z=k_2(k1x+b1)+b2z=k2(k1x+b1)+b2
合并代码就是inline line operator *(const line &o)const {
line res;
res.k = o.k * k % mod;
res.b = (o.k * b + o.b) % mod;
return res;
}( 表示把*this合并到o上 )
-
在splaysplaysplay上因为左子树是深度小于当前点的(原树上就是这个点的上方),右子树是深度大于当前点的(原树上这个点的下方),因为是每个点的值取决于父亲,那么就要从上往下计算.体现在splaysplaysplay上就是把左儿子的线性关系合并到自己上,再把自己的线性关系合并到右二子的线性关系上.对于点xxx上传信息的代码就是
sum[x] = sum[ls] * w[x] * sum[rs];
( w[x]w[x]w[x]表示本点的二元关系,也就是(kx,bx)(k_x,b_x)(kx,bx) )
这样一来,要查一个点与xsfx_{sf}xsf的线性关系就直接splaysplaysplay到根,然后根处储存的线性关系就是要求的.
…(没看懂?多YY下)
那个…还有…这道题可以不用exgcd,直接预处理逆元或者快速幂就行了.
CODE
这题不用换根,不用断边,就没写…
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
char cb[1<<15],*cs=cb,*ct=cb;
#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<15,stdin),cs==ct)?0:*cs++)
template<class T>inline void read(T &res) {
char ch; int flg = 1; for(;!isdigit(ch=getchar());)if(ch=='-')flg=-flg;
for(res=ch-'0';isdigit(ch=getchar());res=res*10+ch-'0'); res*=flg;
}
const int MAXN = 30005;
const int mod = 10007;
int n, q, FA[MAXN], vis[MAXN], inv[mod];
struct line {
int k, b;
line() { k = 1, b = 0; }
inline line operator *(const line &o)const {
line res;
res.k = o.k * k % mod;
res.b = (o.k * b + o.b) % mod;
return res;
}
inline int f(int x) { return (k * x + b) % mod; }
};
namespace LCT {
#define ls ch[x][0]
#define rs ch[x][1]
int ch[MAXN][2], fa[MAXN], sf[MAXN];
line sum[MAXN], w[MAXN];
inline bool isr(int x) { return ch[fa[x]][0] != x && ch[fa[x]][1] != x; }
inline bool get(int x) { return ch[fa[x]][1] == x; }
inline void upd(int x) {
sum[x] = sum[ls] * w[x] * sum[rs];
}
inline void rot(int x) {
int y = fa[x], z = fa[y];
bool l = get(x), r = l^1;
if(!isr(y)) ch[z][get(y)] = x;
fa[ch[x][r]] = y, fa[y] = x, fa[x] = z;
ch[y][l] = ch[x][r], ch[x][r] = y;
upd(y), upd(x);
}
inline void splay(int x) {
for(; !isr(x); rot(x))
if(!isr(fa[x])) rot(get(x) == get(fa[x]) ? fa[x] : x);
}
inline void access(int x) { int y = 0;
for(; x; x=fa[y=x]) splay(x), ch[x][1] = y, upd(x);
}
inline int sert(int x) { //search_root
access(x), splay(x);
while(ch[x][0]) x=ch[x][0];
return x;
}
inline int query(int x) {
int rt = sert(x);
access(sf[rt]), splay(sf[rt]);
int k = sum[sf[rt]].k, b = sum[sf[rt]].b;
bool flg = 0;
if(k == 1) {
if(b) return -1; //无解
flg = 1; //多解的情况还要继续讨论
}
int val_sf = k ? (mod-b) * inv[k-1] % mod : b; //求出了x_sf的值
access(x), splay(x);
if(flg) {
if(!sum[x].k) return sum[x].b; //系数为0就不是多解
else return -2; //否则多解
}
return sum[x].f(val_sf);
}
inline void modify(int x, int y, int K, int B) {
int rt = sert(x);
w[x].k = K, w[x].b = B, upd(x);
if(x == rt) sf[x] = 0;
else {
access(x), splay(x);
ch[x][0] = fa[ch[x][0]] = 0, upd(x);
if(sert(sf[rt]) != rt) {
access(rt), splay(rt);
fa[rt] = sf[rt], sf[rt] = 0;
}
}
access(x), splay(x);
if(sert(y) == x) sf[x] = y;
else fa[x] = y;
}
}
using namespace LCT;
int cur;
void DFS(int x) {
vis[x] = cur;
if(vis[FA[x]] == cur) { sf[x] = FA[x]; return; }
fa[x] = FA[x];
if(!vis[FA[x]]) DFS(FA[x]);
}
inline void pre() {
inv[0] = inv[1] = 1;
for(int i = 2; i < mod; ++i)
inv[i] = (mod - mod/i) * inv[mod%i] % mod;
}
int main () {
pre(); read(n);
for(int i = 1, K, B; i <= n; ++i) {
read(K), read(FA[i]), read(B);
w[i].k = K, w[i].b = B;
}
for(int i = 1; i <= n; ++i)
if(!vis[i]) ++cur, DFS(i);
read(q);
char s; int x, y, K, B;
while(q--) {
while(!isalpha(s=getchar()));
read(x);
if(s == 'A') printf("%d\n", query(x));
else {
read(K), read(y), read(B);
modify(x, y, K, B);
}
}
}