Sky 要上树

看到这个式子，显然是个计数问题。要考虑这条链上每条边的贡献次数。这时候不妨暴力打一下，出个表。比如下面这个
1 1 2 4 8
1 3 8 20
2 8 26
4 20
8

第i行第j列表示长度为i+j-1的链上第j边会被计算多少次。

很容易发现

[V(i,j)= frac{sum_{x le i,y le j,且(x,y) eq (i,j)}^{}V（x，y） }{2} ]

不会证明，但是很容易发现。。

然后这就是个很简单的计数问题了。因为n很小，每次询问可以暴力跳lca，把每条边贡献都算出来
时间复杂度(O（n^2+qn）)

#include<bits/stdc++.h>
#define rep(i,j,k) for(register int i(j);i<=k;++i)
#define drp(i,j,k) for(register int i(j);i>=k;--i)
using namespace std;
typedef long long lxl;
template<typename T>
inline T  max(T &a, T &b) {
	return a > b ? a : b;
}
template<typename T>
inline T  min(T &a, T &b) {
	return a < b ? a : b;
}
inline char gt() {
	static char buf[1 << 21], *p1 = buf, *p2 = buf;
	return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
}
template <typename T>
inline void  read(T &x) {
	register char ch = gt();
	x = 0;
	int w(0);
	while(!(ch >= '0' && ch <= '9'))w |= ch == '-', ch = gt();
	while(ch >= '0' && ch <= '9')x = x * 10 + (ch & 15), ch = gt();
	w ? x = ~(x - 1) : x;
}
template <typename T>
inline void out(T x) {
	if(x < 0) x = -x, putchar('-');
	char ch[20];
	int num(0);
	while(x || !num) ch[++num] = x % 10 + '0', x /= 10;
	while(num) putchar(ch[num--]);
	putchar('
');
}

const int MX = 2e3 + 79;
const int mod = 1e9 + 7;
struct graph {
	int next[MX << 1], head[MX], tot, ver[MX << 1], edge[MX << 1];
	inline void add(int a, int b, int c) {
		ver[++tot] = b;
		next[tot] = head[a];
		edge[tot] = c;
		head[a] = tot;
	}
} G;
int n, dep[MX << 1], fa[MX << 1], dis[MX << 1];
inline void dfs(int x) {
	for(register int i(G.head[x]); i; i = G.next[i]) {
		int y = G.ver[i], z = G.edge[i];
		if(y == fa[x]) continue;
		dep[y] = dep[x] + 1;
		dis[y] = z;
		fa[y] = x;
		dfs(y);
	}
}
inline int LCA(int x, int y) {
	if(dep[x] < dep[y]) swap(x, y);
	while(dep[x] != dep[y]) x = fa[x];
	while(x != y) x = fa[x], y = fa[y];
	return x;
}
int val[MX][MX], sum[MX][MX];


int main() {
	freopen("tree.in", "r", stdin);
	freopen("tree.out", "w", stdout);
	read(n);
	int u, v, w;
	rep(i, 2, n) {
		read(u);
		read(v);
		read(w);
		G.add(u, v, w);
		G.add(v, u, w);
	}
	dfs(1);
	val[1][1] = sum[1][1] = 1;
	rep(i, 1, n)
	rep(j, 1, n) {
		val[i][j] += (1ll * sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + mod) % mod;
		sum[i][j] += 2ll * (1ll * sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + mod) % mod;
	}
	int q;read(q);
	while(q--){
		read(u);read(v);
		int lca=LCA(u,v);
		int ans(0);
		if(lca==u||lca==v){
			if(dep[u]>dep[v]) swap(u,v);
			int len=dep[v]-dep[u],i=1;
			while(u!=v){
				ans+=1ll*dis[v]*val[i][len-i+1]%mod;
				if(ans>=mod) ans-=mod;
				++i;
				v=fa[v];
			}
		}
		else{
			int len=dep[v]+dep[u]-2*dep[lca],i=1;
			while(u!=lca){
				ans+=1ll*dis[u]*val[i][len-i+1]%mod;
				if(ans>=mod) ans-=mod;
				++i;
				u=fa[u];
			}
			i=1;
			while(v != lca) {
				ans += 1LL * dis[v] * val[i][len - i + 1] % mod;
				if(ans >= mod) ans -= mod;
				++ i;
				v = fa[v];
			}
		}
		out(ans);
	}
	return 0;
}