1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
|
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
#define mo (int)(1e9 + 7)
#define N 300010
struct node { int y, z; };
struct quey { int x, id; };
vector<node>G[N];
vector<quey>E[N];
int n, m, i, j, k, T, u, v, w, ans[N];
int dfn[N], dep[N];
struct Segment_tree {
#define ls (k << 1)
#define rs (k << 1 | 1)
#define mid ((l + r) >> 1)
int mn[N << 2], s[N << 2], ans[N << 2];
pair<int, int> que(int k, int l, int r, int x, int y, int lst) {
if(l >= x && r <= y) {
if(l == r) return {s[k] * lst, mn[k]};
if(lst <= mn[k]) return {s[k] * lst, mn[k]};
if(lst <= mn[ls]) {
auto t = que(rs, mid + 1, r, x, y, lst);
int sum = s[ls] * lst + t.fi;
return {sum, min(lst, mn[k])};
}
else {
auto t = que(ls, l, mid, x, y, lst);
int sum = t.fi + ans[k] - ans[ls];
return {sum, min(lst, mn[k])};
}
return {0, 0};
}
int sum = 0, mx = 1e18;
if(x <= mid) {
auto t = que(ls, l, mid, x, y, lst);
sum += t.fi; mx = t.se;
}
if(y >= mid + 1) {
auto t = que(rs, mid + 1, r, x, y, min(lst, mx));
sum += t.fi; mx = min(mx, t.se);
}
return {sum, mx};
}
void push_up(int k, int l, int r) {
s[k] = s[ls] + s[rs];
mn[k] = min(mn[ls], mn[rs]);
ans[k] = ans[ls] + que(rs, mid + 1, r, mid + 1, r, mn[ls]).fi;
}
void set(int k, int l, int r, int x, int Mn, int S) {
if(l == r) {
mn[k] = Mn; s[k] = S; ans[k] = 0;
return ;
}
if(x <= mid) set(ls, l, mid, x, Mn, S);
else set(rs, mid + 1, r, x, Mn, S);
push_up(k, l, r);
}
#undef ls
#undef rs
#undef mid
}Seg;
void dfs1(int x, int fa) {
dep[x] = dep[fa] + 1;
for(auto t : G[x]) if(t.y != fa) dfs1(t.y, x);
}
void dfs2(int x, int fa, int w) {
dfn[x] = dep[x];
Seg.set(1, 1, n, dfn[x], x, w);
for(auto t : G[x]) if(t.y != fa) dfs2(t.y, x, t.z);
for(auto t : E[x]) {
int y = t.x;
if(dfn[y] <= 0) { ans[t.id] = -1; continue; }
ans[t.id] = Seg.que(1, 1, n, dfn[y] + 1, dfn[x], y).fi;
}
dfn[x] = -1;
}
signed main()
{
freopen("tree.in", "r", stdin);
freopen("tree.out", "w", stdout);
n = read(); m = read();
for(i = 1; i < n; ++i) {
u = read(); v = read(); w = read();
G[u].pb({v, w}); G[v].pb({u, w});
}
dfs1(1, 0);
for(i = 1; i <= m; ++i) {
u = read(); v = read();
if(u == v) { ans[i] = 0; continue; }
E[v].pb({u, i});
}
dfs2(1, 0, 0);
for(i = 1; i <= m; ++i) printf("%lld\n", ans[i]);
return 0;
}
|
