C++14(g++5.4) 解法, 执行用时: 339ms, 内存消耗: 19160K, 提交时间: 2018-08-02 09:35:24

#include<cstdio>
#include<vector>
using namespace std;
struct edge
{
	int x,y,z,l;
}e[100005];
struct p
{
	int s,t,ans;
}ta[100005];
int n,i,m,dp[2][100005],dsu[100005],vis[100005],ans=0;
const int mod=1e9+7;
vector<int> s[100005];
vector<int> ss[100005];
int other1(int p,int id){return e[id].x==p?e[id].y:e[id].x;}
int other2(int p,int id){return ta[id].s==p?ta[id].t:ta[id].s;}
int get(int p){return dsu[p]==p?p:dsu[p]=get(dsu[p]);}
void dfs(int p)
{
	int i,v,u,f;
	edge h;
	vis[p]=1;
	for(i=0;i<ss[p].size();i++)
	{
		v=ss[p][i];
		u=other2(p,v);
		if(vis[u]==0)continue;
		f=get(u);
		ta[v].ans=((1LL*ans+1LL*dp[0][u]+1LL*dp[0][p]-dp[1][u]-dp[1][p]-2LL*dp[0][f]+2LL*dp[1][f])%mod+mod)%mod;
	}
	for(i=0;i<s[p].size();i++)
	{
		v=s[p][i];
		u=other1(p,v);
		if(vis[u])continue;
		dp[0][u]=dp[0][p];
		dp[1][u]=dp[1][p];
		if(e[v].l%2)dp[1][u]=(dp[1][u]+e[v].z)%mod;
		else dp[0][u]=(dp[0][u]+e[v].z)%mod;
		dfs(u);
		dsu[u]=p;
	}
}
int main()
{
	scanf("%d",&n);
	for(i=1;i<=n;i++)dsu[i]=i;
	for(i=1;i<n;i++)
	{
		scanf("%d%d%d%d",&e[i].x,&e[i].y,&e[i].z,&e[i].l);
		s[e[i].x].push_back(i);
		s[e[i].y].push_back(i);
		ans=(ans+1LL*e[i].z*(e[i].l+e[i].l%2))%mod;
	}
	scanf("%d",&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&ta[i].s,&ta[i].t);
		if(ta[i].s==ta[i].t)ta[i].ans=ans;
		else
		{
			ss[ta[i].s].push_back(i);
			ss[ta[i].t].push_back(i);
		}
	}
	dfs(1);
	for(i=1;i<=m;i++)printf("%d\n",ta[i].ans);
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 190ms, 内存消耗: 11108K, 提交时间: 2020-03-29 12:02:56

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
const int mod=1000000007;
int n,m,s,dep[N],fa[N],top[N],siz[N];
int head[N<<1],to[N<<1],nxt[N<<1],num[N<<1],e;
long long dis[N],w[N<<1];
inline void add(int u,int v,long long z,int l)
{
	to[++e]=v,w[e]=z,num[e]=l,nxt[e]=head[u],head[u]=e;
}
void dfs(int u)
{
	int i,maxs=0,son=0;
	top[u]=u,siz[u]=1;
	for(i=head[u];i;i=nxt[i])
	{
		int v=to[i];
		if(v==fa[u]) continue;
		fa[v]=u,dep[v]=dep[u]+1;
		dis[v]=(dis[u]+((num[i]&1)?1:-1)*w[i])%mod;
		dfs(v);
		siz[u]+=siz[v];
		if(siz[v]>maxs) maxs=siz[son=v];
	}
	if(son) top[son]=u;
}
int find(int u)
{
	return top[u]=top[u]==u?u:find(top[u]);
}
int LCA(int u,int v)
{
	if(find(u)!=find(v))
	return dep[top[u]]>dep[top[v]]?LCA(fa[top[u]],v):LCA(u,fa[top[v]]);
	else return dep[u]>dep[v]?v:u;
}
int main()
{
	scanf("%d",&n);
	int u,v,l;
	long long z;
	long long sum=0,ans;
	for(int i=1;i<n;++i)
	{
		scanf("%d%d%lld%d",&u,&v,&z,&l),add(u,v,z,l),add(v,u,z,l);
		sum=(sum+(l+(l&1))*z%mod)%mod;
	}
	scanf("%d",&m);
	dis[1]=0,dfs(1);
	while(m--)
	{
		scanf("%d%d",&u,&v);
		int lca=LCA(u,v);
		printf("%lld\n",((sum+2*dis[lca]-dis[u]-dis[v])%mod+mod)%mod);
	}
	return 0;
}