C++14(g++5.4) 解法, 执行用时: 329ms, 内存消耗: 40644K, 提交时间: 2019-04-20 15:58:51

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 1e5 + 10;
int n, q;
int f[MAXN][20], dep[MAXN];
ll sum1[MAXN], sum2[MAXN], ans;
ll dp[MAXN], dp2[MAXN], h[MAXN][20];
ll sch[MAXN];

struct edge { int to, w, c; };
vector<edge> e[MAXN];

void dfs(int p) {
	dep[p] = dep[f[p][0]] + 1;
	for (int i = 1; i < 20; ++i) f[p][i] = f[f[p][i - 1]][i - 1];
	for (auto c : e[p]) {
		if (c.to == f[p][0])continue;
		f[c.to][0] = p;
		sum1[c.to] = sum1[p] + c.w;
		sum2[c.to] = sum2[p] + c.w - c.c;
		dp[c.to] = c.w - c.c;
		dfs(c.to);
		dp[p] += dp[c.to];
		sch[p] += dp[c.to];
	}
	dp[p] = max<ll>(dp[p], 0);
}

void dfs2(int p) {
	ll su = 0;
	h[p][0] = dp2[p];
	for (int i = 1; i < 20; ++i)
		h[p][i] = h[p][i - 1] + h[f[p][i - 1]][i - 1];
	for (auto c : e[p]) {
		if (c.to == f[p][0])continue;
		su += dp[c.to];
	}
	for (auto c : e[p]) {
		if (c.to == f[p][0])continue;
		dp2[c.to] = su - dp[c.to];
		dfs2(c.to);
	}
}

int lca(int x, int y) {
	if (dep[x] < dep[y]) swap(x, y);
	for (int i = 19, t = dep[x] - dep[y]; i >= 0; i--)
		if (t >> i & 1) x = f[x][i];
	if (x == y) return x;
	for (int i = 19; i >= 0; --i)
		if (f[x][i] != f[y][i]) {
			x = f[x][i]; y = f[y][i];
		}
	return f[x][0];
}

int jump(int x, int y) {
	for (int i = 19; i >= 0; --i)
		if (dep[f[x][i]] > dep[y]) {
			ans += h[x][i];
			x = f[x][i];
		}
	return x;
}

int main() {
	scanf("%d%d", &n, &q);
	for (int i = 1; i < n; ++i) {
		int l, r, w, c;
		scanf("%d%d%d%d", &l, &r, &w, &c);
		e[l].push_back({ r, w, c });
		e[r].push_back({ l, w, c });
	}
	dfs(1);
	dfs2(1);
	while (q--) {
		int x, y; scanf("%d%d", &x, &y);
		if (x == y) {
			printf("%lld\n", sch[x]); continue;
		}
		int o = lca(x, y);
		ans = sum2[x] - sum2[o] + sum1[y] - sum1[o];
		int px = jump(x, o);
		int py = jump(y, o);
		ans += sch[o];
		if (px != o) {
			ans -= dp[px];
			ans += sch[x];
		}
		if (py != o) {
			ans -= dp[py];
			ans += sch[y];
		}
		printf("%lld\n", ans);
	}
}

C++11(clang++ 3.9) 解法, 执行用时: 484ms, 内存消耗: 45000K, 提交时间: 2019-04-19 21:45:06

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int _=1e5+5;
ll n,Q,f[_],g[_],st[18][_],A[18][_],fz[_],gz[_],dep[_],ans;
struct edge{int v,w,c;};
vector<edge>e[_];
void dfs(int fa,int u){
	for(edge p:e[u]){
		int v=p.v;if(v==fa)continue;
		g[v]=p.w-p.c;
		fz[v]=fz[u]+p.w; gz[v]=gz[u]+p.c;
		dfs(u,v); f[u]+=g[v];
	}
	g[u]=max(0ll,g[u]+f[u]);
}
void Dfs(int fa,int u){
	st[0][u]=fa; A[0][u]=f[fa]-g[u]; dep[u]=dep[fa]+1;
	for(edge p:e[u]){
		int v=p.v;if(v==fa)continue;
		Dfs(u,v);
	}
}
void init(){
	for(int i=1;i<=17;++i)
		for(int j=1;j<=n;++j){
			st[i][j]=st[i-1][st[i-1][j]];
			A[i][j]=A[i-1][j]+A[i-1][st[i-1][j]];
		}
}
int lca(int x,int y){
	if(dep[x]<dep[y])swap(x,y);
	for(int i=17;~i;--i)
		if(dep[st[i][x]]>=dep[y])
			ans+=A[i][x],x=st[i][x];
	if(x==y)return x;
	for(int i=17;~i;--i)
		if(st[i][x]!=st[i][y]){
			ans+=A[i][x]+A[i][y];
			x=st[i][x],y=st[i][y];
		}
	ans+=A[0][x]+A[0][y];
	return st[0][x];
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>Q;
	for(int i=1;i<n;++i){
		int u,v,w,c;cin>>u>>v>>w>>c;
		e[u].push_back((edge){v,w,c});
		e[v].push_back((edge){u,w,c});
	}
	dfs(0,1);Dfs(0,1); init();
	while(Q--){
		int u,v,x;cin>>u>>v;ans=0; x=lca(u,v);
		cout<<ans+f[u]+f[v]+(fz[u]+fz[v]-fz[x]*2)-f[x]-(gz[u]-gz[x])<<endl;
	}
}