ABC133 F Colorful Tree 最近公共祖先(LCA)+树形策略记忆化搜索
题目
给个顶点组成的一棵树，给边先着色并赋权（赋距离）。
现给定问题集，第个问题是：
假设把颜色为的所有线段的长度统一改为
，求从
顶点到
顶点的最小距离。
考察
考察内容
如果用在线算法寻找每个问题的解，会TLE。若用离线算法，用字符串记忆所有节点的路径并两两比较，会同时TLE和MLE。所以这里我们需要谨慎考虑时间复杂度和空间复杂度。
- 使用Tarjan的离线LCA算法是这题的首选。进行第一次树形探索。
)
- 使用Tarjan后用map<pii,int>记录所有LCA的解。
)
- 将每组u,v和LCA(u,v)需要计算的颜色标记在树形顶点中，这里用map数组，key为颜色，value为当前顶点前的当前颜色的总距离和总线段数量。
)
- 开一个距离全局变量和两个dp全局数组（记录到当前顶点为止的总距离，以及颜色c下的总距离和颜色c下的总线段数量）
)
- 进行第二次树形探索。计算所有标记好的一个顶点的map里所有的value。
)
- 遍历问题集，搜索顶点map信息并计算答案。
)
代码实现
//---------------------
#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 set
REP(i,MAXUF){
uf_par[i]=uf_val(i);
uf_rank[i]=1;
}
}
uf_val uf_find(const uf_val& a){ // Find parent
return (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;
}
