(离线做法)ABC133F 题解

题目链接：ABC133F

明确维护目标

显然我强制修改强制查询的在线做法会超时，于是我考虑离线做法。

首先我们可以知道，树上的路径可以用和差关系线性表示。例如我以1节点为根节点，那么可以将 u 到 v 的距离表示为$dis_{1,u} + dis_{1,v}-2 dis_{1,lca_{u,v}} $

那么我修改 col 这个颜色后，会对答案有什么影响呢。

显然他只会对 col 这个颜色的边产生影响。

假设原来 u 到 v 路径上会经过 k 个 col 的边

初步离线思想：

最开始思路是很正确的，维护某条路径上走过 id 有多少次以及长度，但是开数组$a_{i,j}$表示在 i 点处 j 的颜色的贡献，会超过空间。
而且呢，因为继承原因，每次要 n 的时间把父亲节点的复制到子节点，这样花费$n$时间,$n^2$会超时间。

实现给卡住了，如果在线的话，树剖忘记怎么打了，就会很悲伤。

离线思想更新

离线可以做，具体思路是这样的：
我可以统计出每个询问他需要的颜色，顶点（u,v,$\ lca$),显然这三个我都需要求在这种颜色下的经过此颜色边的次数以及长度。
于是我对某个顶点x绑询问信息：$(i , col)$，表示我要在顶点x查询第i组询问有关col颜色的所有信息。
但是所有信息，我必须要具体知道在i组询问中，x这个点是u吗，是v吗，还是$lca$。（毕竟$lca$是减去两次计算，但是u,v是加上，不一样）
因此捆绑$（i，col，1/2/3)$，$1/2/3$分别代表我要查询的目标。遇到相应的op，那么i组相应的位置变化就好了

代码：

#include<bits/stdc++.h>
using namespace std;
/*
想法是利用和差关系统计1节点到所有点所经过的id相同的有多少个
然后平生第一次遇到可能会超过空间

*/
int n,q;
int colcs[100005];
int coldis[100005];
int askcs[100005];
int askdis[100005];

int dis[100005];
struct nd{
	int id;
	int col;
	int op;//是u/v还是lca（1/2/3） 
};
vector<nd>need[100005];
struct nod{
	int id;
	int changeval;
	int u;
	int v;
}line[100005];
struct node{
	int to;
	int id;
	int val;
};
vector<node>mp[100005];
//vector< pair<int,int> >csm[100005];
struct ak{
	int id;
	int u;
};
vector<ak>ask[100005];
struct as{
	int lcacs;
	int lcadis;
	int ucs;
	int udis;
	int vcs;
	int vdis;
}ans[1000005];


int fat[100005];
bool vis[100005];
int lca[100005];
int finda(int x){
	if(fat[x]==x){
		return x;
	}
	else{
		fat[x]=finda(fat[x]);
		return fat[x];
	}
}
void unite(int x,int y){
	x=finda(x);
	y=finda(y);
	if(x==y){
		return;
	}
	else{
		fat[x]=y;
	}
}
void tarjan(int x,int fa){
	vis[x]=1;
	for(int i=0;i<mp[x].size();i++){
		int to=mp[x][i].to;
		if(to==fa){
			continue;
		}
		tarjan(to,x);
		unite(to,x);
	}
	
	for(int i=0;i<ask[x].size();i++){
		int tx=ask[x][i].u;
		if(!vis[tx]){
			continue;
		}
		lca[ask[x][i].id]=finda(tx);
	}
}
void dfs(int x,int fa){
	for(int i=0;i<mp[x].size();i++){
		int to=mp[x][i].to;
		if(to==fa){
			continue;
		}
		colcs[mp[x][i].id]++;
		coldis[mp[x][i].id]+=mp[x][i].val;
		dis[to]=dis[x]+mp[x][i].val;
		dfs(to,x);
		colcs[mp[x][i].id]--;
		coldis[mp[x][i].id]-=mp[x][i].val;
	}
	for(int i=0;i<need[x].size();i++){
		int co=need[x][i].col;
		int op=need[x][i].op;
		int id=need[x][i].id;
		if(op==1){
			ans[id].ucs=colcs[co];
			ans[id].udis=coldis[co];
		}
		else if(op==2){
			ans[id].vcs=colcs[co];
			ans[id].vdis=coldis[co];
		}
		else{
			ans[id].lcacs=colcs[co];
			ans[id].lcadis=coldis[co];
		}
	}
}
int las=0;


int main(){
//	freopen("jett.in","r",stdin);
//	freopen("jett.out","w",stdout);
	cin >> n >> q;
	bool tepan=1;
	las=0; 
	for(int i=1;i<=n-1;i++){
		fat[i]=i;
		int u,v,id,t;
		cin >> u >> v >> id >> t;
		mp[u].push_back((node){v,id,t});
		mp[v].push_back((node){u,id,t});
		if(!las){
			las=id;
		}
		else if(las!=id){
			tepan=0;
		}
//		csm[id].push_back(make_pair(u,v));
	}
	fat[n]=n;
	
	for(int i=1;i<=q;i++){
		int x,y,a,b;
		cin >> x >> y >> a >> b;//id为x的全部边，时间在此次变为y ，求a到b需要花费的时间,显然利用和差关系求解即可 
		ask[a].push_back((ak){i,b});
		ask[b].push_back((ak){i,a});
		line[i].u=a;
		line[i].v=b;
		line[i].id=x;
		line[i].changeval=y;
	}
	tarjan(1,1);
	for(int i=1;i<=q;i++){
		need[line[i].u].push_back((nd){i,line[i].id,1});
		need[line[i].v].push_back((nd){i,line[i].id,2});
		need[lca[i]].push_back((nd){i,line[i].id,3});
	}
	dfs(1,1);
	for(int i=1;i<=q;i++){
		int u=line[i].u;
		int v=line[i].v;
		int zdis=dis[line[i].u]+dis[line[i].v]-2*dis[lca[i]];
		int k1=ans[i].ucs+ans[i].vcs-2*ans[i].lcacs;
		int kw=ans[i].udis+ans[i].vdis-2*ans[i].lcadis;
		int cha=line[i].changeval*k1-kw;
		cout<<zdis+cha<<endl;
	}
	
}