ABC133 F Colorful Tree 最近公共祖先(LCA)+樹(shù)形策略記憶化搜索
題目
給個(gè)頂點(diǎn)組成的一棵樹(shù)作岖，給邊先著色并賦權(quán)（賦距離）。
現(xiàn)給定問(wèn)題集胁住，第個(gè)問(wèn)題是：
假設(shè)把顏色為的所有線段的長(zhǎng)度統(tǒng)一改為
趁猴，求從
頂點(diǎn)到
頂點(diǎn)的最小距離。
考察
考察內(nèi)容
如果用在線算法尋找每個(gè)問(wèn)題的解彪见，會(huì)TLE儡司。若用離線算法，用字符串記憶所有節(jié)點(diǎn)的路徑并兩兩比較余指，會(huì)同時(shí)TLE和MLE捕犬。所以這里我們需要謹(jǐn)慎考慮時(shí)間復(fù)雜度和空間復(fù)雜度。
- 使用Tarjan的離線LCA算法是這題的首選酵镜。進(jìn)行第一次樹(shù)形探索碉碉。
)
- 使用Tarjan后用map<pii,int>記錄所有LCA的解。
)
- 將每組u,v和LCA(u,v)需要計(jì)算的顏色標(biāo)記在樹(shù)形頂點(diǎn)中淮韭，這里用map數(shù)組垢粮，key為顏色，value為當(dāng)前頂點(diǎn)前的當(dāng)前顏色的總距離和總線段數(shù)量靠粪。
)
- 開(kāi)一個(gè)距離全局變量和兩個(gè)dp全局?jǐn)?shù)組（記錄到當(dāng)前頂點(diǎn)為止的總距離蜡吧，以及顏色c下的總距離和顏色c下的總線段數(shù)量）
)
- 進(jìn)行第二次樹(shù)形探索毫蚓。計(jì)算所有標(biāo)記好的一個(gè)頂點(diǎn)的map里所有的value。
)
- 遍歷問(wèn)題集昔善，搜索頂點(diǎn)map信息并計(jì)算答案元潘。
)
代碼實(shí)現(xiàn)
//---------------------
#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;
}
