xyd 模拟赛的题，感觉非常 Educational。
Description
给定一颗 \(n\) 个节点的树，每个节点有 \(a_i\) 个石子和权值 \(b_i\)。
Alice 和 Bob 每次选定两个星球 \(u\) 和 \(v\)，游戏在 \(u\) 和\(v\) 间路径上的所有节点进行，Alice 先手。一次操作可以选择路径上的一个还有石子的节点，并取走任意一个石子，或取走任意两个相邻的石子。一次操作后，原本连续的一行石子可能会被分成两段独立的子游戏，取到最后一颗石子的玩家赢。
Bob 在游戏开始前，可以拿走路径上任意数量星球的石子。从第 \(i\) 个节点每拿一个石子，需要代价 \(b_i\)。修改后，剩下的石子会重新排成连续的一列。
Bob 希望通过预先的修改，使得在接下来的比赛中他拥有必胜策略，他希望你能计算出达成这一目标所需的最小总代价。
有时 \(a_i\) 和 \(b_i\) 可能会变化。请维护修改并回答询问。
\(n,q \le 5 \times 10^4,a_i,b_i \le 10^9\)。
Solution
对 SG 函数打表，发现 SG 函数从 \(72\) 往后出现循环，循环节为 \(12\)。但循环本身并没有好的规律。
注意到 SG 函数异或后的可能值不超过 \(16\)，考虑 DP。把链拍到序列上，定义 \(f_{i,j}\) 表示位置 \(i\) 最终异或和为 \(j\) 的答案，则 \(f_{i,j}=\min{f_{i-1,k}+v_{i,j \oplus k}}\)。\(v_{i,j}\) 表示把 \(i\) 的 SG 值变为 \(j\) 的最小代价。
发现各位间相互独立，且每次转移都是 \((\min,+)\) 卷积的形式，可以快速合并。因此对每个位置维护好 \(v\) 就可以在链上一路合并上去再合并下来。不难联想到同样的线段树维护矩阵，用线段树维护卷积过程即可。时间复杂度 \(O(q V^2 \log^2 n)\)，其中 \(V=16\)。
Code
#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(int)(b);i++)
#define pb emplace_back
#define inf 1e18
#define lb(x) ((x) & -(x))
using namespace std;
const int N=1e5+10;
const int vl[73]={0,1,2,3,1,4,3,2,1,4,2,6,4,1,2,7,1,4,3,2,1,4,6,7,4,1,2,8,5,4,7,2,1,8,6,7,4,1,2,3,1,4,7,2,1,8,2,7,4,1,2,8,1,4,7,2,1,4,2,7,4,1,2,8,1,4,7,2,1,8,6,7,4};
const int gl[12]={4,1,2,8,1,4,7,2,1,8,2,7};
int sg(int x){return (x<=72)?vl[x]:gl[x%12];}
int to[100][20],val[12][20];int n,q,a[N],b[N];
vector<int> G[N];int fa[N],dep[N],sz[N],hs[N],pre[N];
int idx,dfn[N],rnk[N],top[N];
void dfs1(int x,int f)
{pre[x]=pre[f]^sg(a[x]);fa[x]=f,dep[x]=dep[f]+1,sz[x]=1,hs[x]=-1;for(auto y:G[x]){if(y==f) continue;dfs1(y,x);sz[x]+=sz[y];if(hs[x]==-1||sz[hs[x]]<sz[y]) hs[x]=y;}
}
void dfs2(int x,int t)
{dfn[x]=++idx,rnk[idx]=x,top[x]=t;if(hs[x]==-1) return;dfs2(hs[x],t);for(auto y:G[x]) if(y!=fa[x]&&y!=hs[x]) dfs2(y,y);
}struct node // 重载卷积
{int f[1<<4];node(){rep(i,0,15) f[i]=inf;}void clear(){rep(i,0,15) f[i]=inf;}node operator *(const node &x) const{node res;rep(i,0,15) rep(j,0,15) res.f[i^j]=min(res.f[i^j],f[i]+x.f[j]);return res;}
}I; // I 是单位元
void print(const node &x)
{rep(i,0,15) cout<<x.f[i]<<" ";cout<<"\n";
}
void get(node &t,int x,int y)
{t.clear();if(x<=84){rep(i,0,15) if(to[x][i]!=inf) t.f[i]=min(t.f[i],to[x][i]*y);}elserep(i,0,15){if(val[x%12][i]!=inf) t.f[i]=min(t.f[i],val[x%12][i]*y);if(to[84][i]!=inf) t.f[i]=min(t.f[i],(to[84][i]+x-84)*y);}
}
#define lc x<<1
#define rc x<<1|1
#define mid ((l+r)>>1)
struct segtree
{node t[N<<2];void up(int x){t[x]=t[lc]*t[rc];}void build(int x,int l,int r){if(l==r) return get(t[x],a[rnk[l]],b[rnk[l]]);build(lc,l,mid),build(rc,mid+1,r);up(x);}void update(int x,int l,int r,int p,int a,int b){if(l==r) return get(t[x],a,b);if(p<=mid) update(lc,l,mid,p,a,b);else update(rc,mid+1,r,p,a,b);up(x);}node query(int x,int l,int r,int L,int R){if(L<=l&&r<=R) return t[x];node res=I;if(L<=mid) res=res*query(lc,l,mid,L,R);if(mid+1<=R) res=res*query(rc,mid+1,r,L,R);return res;}
}tr;int query(int x,int y)
{node res=I;while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]]) swap(x,y);res=res*tr.query(1,1,n,dfn[top[x]],dfn[x]);x=fa[top[x]];}if(dfn[x]>dfn[y]) swap(x,y);res=res*tr.query(1,1,n,dfn[x],dfn[y]);return res.f[0];
}
signed main()
{freopen("interstellar.in","r",stdin);freopen("interstellar.out","w",stdout);ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);I.f[0]=0;rep(i,1,84){rep(j,0,15) to[i][j]=inf;rep(j,0,i) to[i][sg(j)]=i-j;}rep(i,0,11){rep(j,0,15) val[i][j]=inf;rep(j,i+1,11) val[i][gl[j]]=12-j+i;rep(j,0,i) val[i][gl[j]]=i-j;}cin>>n;rep(i,1,n) cin>>a[i];rep(i,1,n) cin>>b[i];rep(i,1,n-1){int u,v; cin>>u>>v;G[u].pb(v),G[v].pb(u);}dfs1(1,0),dfs2(1,1);tr.build(1,1,n);cin>>q;rep(_,1,q){int opt,x,y,z;cin>>opt>>x>>y;if(opt==1) cin>>z,tr.update(1,1,n,dfn[x],y,z);else cout<<query(x,y)<<"\n";}return 0;
}