ABC133 F Colorful Tree 最近公共祖先(LCA)+树形策略记忆化搜索

ABC133 F Colorful Tree 最近公共祖先(LCA)+树形策略记忆化搜索

题目

给$N$个顶点组成的一棵树，给边先着色并赋权（赋距离）。
现给定问题集，第$i$个问题是：
假设把颜色为$x_i$的所有线段的长度统一改为$y_i$，求从$u_i$顶点到$v_i$顶点的最小距离。

考察

考察内容
如果用在线算法寻找每个问题的解，会TLE。若用离线算法，用字符串记忆所有节点的路径并两两比较，会同时TLE和MLE。所以这里我们需要谨慎考虑时间复杂度和空间复杂度。

1. 使用Tarjan的离线LCA算法是这题的首选。进行第一次树形探索。$O(n+q)$
2. 使用Tarjan后用map<pii,int>记录所有LCA的解。$O(n+qlogq)$
3. 将每组u,v和LCA(u,v)需要计算的颜色标记在树形顶点中，这里用map数组，key为颜色，value为当前顶点前的当前颜色的总距离和总线段数量。$O(n+qlogq+3q)$
4. 开一个距离全局变量和两个dp全局数组（记录到当前顶点为止的总距离，以及颜色c下的总距离和颜色c下的总线段数量）$O(n+qlogq+3q+3)$
5. 进行第二次树形探索。计算所有标记好的一个顶点的map里所有的value。 $O(n+qlogq+3q+3+n)$
6. 遍历问题集，搜索顶点map信息并计算答案。$O(n+qlogq+3q+3+n+q)$

代码实现

$O(n+qlogq)$

//---------------------
#define MAXN 100005
//---------------------//==================UF======================
#define MAXUF 100005
typedef ll uf_val;
//---------------------
uf_val uf_par[MAXUF];
ll uf_rank[MAXUF];void uf_init(){
     // Initialize Union-find setREP(i,MAXUF){
    uf_par[i]=uf_val(i);uf_rank[i]=1;}
}uf_val uf_find(const uf_val& a){
     // Find parentreturn (uf_par[a]==a)?(a):(uf_par[a]=uf_find(uf_par[a])); // Compress path
}void uf_unite(const uf_val& a, const uf_val& b){
    auto x = uf_find(a), y = uf_find(b);if(x==y) return;uf_par[y]=x;//if (uf_rank[x]<uf_rank[y]) {uf_par[x]=y; uf_rank[y]+=uf_rank[x];}//else {uf_par[y]=x; uf_rank[x]+=uf_rank[y];}
}bool uf_same(const uf_val& a,const uf_val& b){
    return uf_find(a) == uf_find(b);
}//==================UF======================struct edge{
    int v;int c;int d;
};struct ques{
    int x,y,u,v;
};struct vexdata{
    int dist;int num;
};ques qlist[MAXN];
vector<edge> G[MAXN];
map<int,vexdata> vlist[MAXN];map<pii,int> LCF;
bool LCFfound[MAXN];
vector<int> vqlist[MAXN];int n,q;int memdist;
int memCdist[MAXN];
int memCnum[MAXN];
void preIterate(int lastid, int curid){
    ITE(vlist[curid]){
    ite->second.dist=memCdist[ite->first];ite->second.num=memCnum[ite->first];}vlist[curid][0].dist=memdist;ITE(G[curid]){
    if(ite->v==lastid) continue;memdist+=ite->d;memCdist[ite->c]+=ite->d;memCnum[ite->c]++;preIterate(curid,ite->v);memdist-=ite->d;memCdist[ite->c]-=ite->d;memCnum[ite->c]--;}
}void doLCF(int lastid,int curid){
    LCFfound[curid]=true;ITE(G[curid]){
    if(ite->v==lastid) continue;doLCF(curid,ite->v);	uf_unite(curid,ite->v);}ITE(vqlist[curid]){
    if(LCFfound[*ite]) {
    int tu=curid,tv=*ite;if(tu>=tv) swap(tu,tv);LCF[pii(tu,tv)]=uf_find(*ite);}}
}void solve(){
    REP(i,q){
    int u=qlist[i].u,v=qlist[i].v,x=qlist[i].x,y=qlist[i].y;if(u>=v) swap(u,v);int f=LCF[pii(u,v)];int res = vlist[u][0].dist+vlist[v][0].dist-2*vlist[f][0].dist;int resOrg=vlist[u][x].dist+vlist[v][x].dist-2*vlist[f][x].dist;int resNew=y*(vlist[u][x].num+vlist[v][x].num-2*vlist[f][x].num);cout<<res-resOrg+resNew<<endl;}
}int main(){
    cin>>n>>q;uf_init();REP(i,n-1) {
    int ta,tb,tc,td; cin>>ta>>tb>>tc>>td; G[ta].PB({
    tb,tc,td}); G[tb].PB({
    ta,tc,td});}REP(i,q){
    int tx,ty,tu,tv;cin>>tx>>ty>>tu>>tv;qlist[i]=(ques){
    tx,ty,tu,tv};vqlist[tu].PB(tv);vqlist[tv].PB(tu);}ZERO(memCdist);ZERO(memCnum);REP(i,MAXN) LCFfound[i]=false;doLCF(0,1);vexdata tempdata;REP(i,q){
    int tu=qlist[i].u ,tv=qlist[i].v ,tc=qlist[i].x;if(tu>=tv) swap(tu,tv);vlist[tu][tc]=tempdata;vlist[tv][tc]=tempdata;vlist[LCF[pii(tu,tv)]][tc]=tempdata;}REP1(i,n) vlist[i][0]=tempdata;preIterate(0,1);solve();return 0;
}