\[Output
For every query, please output the number of days on a separate line.
Constraints
$1 ≤ N, M ≤ 100000$
$1 ≤ X, Y, S, F ≤ N$
$1 ≤ D ≤ 2$
$2 ≤ P ≤ 2*N$
##Example
###Input:
```dos
5
1 2 1
2 3 2
1 4 2
4 5 1
5
1 5 3
1 3 2
2 5 4
1 2 10
4 5 2
```
###Output:
```dos
1
2
1
1
1
```
##Solution
翻譯一下題意:
>有一棵每条边的边权分别为$1$或$2$的共有$n$个节点的树, 对于一个询问, 给出起点$u$和终点$v$, 以及每一天最多走的路程$k$. 规定每天的结束点必须在树的节点上, 问最少要几天走完所有路程.

由於邊的權值只能為$1$或$2$, 因此可以考慮採用時間複雜度帶根號的算法.
>对$p$分情况进行讨论
>1. $p \ge \sqrt{n}$
>最多总共走$\sqrt{n}$天, 对于每一天倍增最远可以走到哪里即可, 并统计走的天数.
>2. $p \le sqrt(n)$
>对于每次询问的$p$, 暴力求出从每个点出发, 最多走$p$距离最远可以到达的最远位置. 再用倍增求出$f[i][j]$数组, 表示从点$i$出发, 走$2 ^ j$天可以到达的最远位置. 最后跑一次倍增解决.
>注意在进行这种计算之前, 先要将$p$从小到大排序. 这样每次计算就可以省去之前已经进行过的部分. 同时, 对于两个相同的$p$值, 不要重复求$f$数组, 否则会超时.

>时间复杂度$O \left( n * \sqrt{n} * log(n) \right)$

```cpp
#include<cstdio>
#include<cctype>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

inline int read()
{
int x = 0, flag = 1;
char c;
while(! isdigit(c = getchar()))
if(c == '-')
flag *= - 1;
while(isdigit(c))
x = x * 10 + c - '0', c = getchar();
return x * flag;
}

void println(int x)
{
if(x < 0)
putchar('-'), x *= - 1;
if(x == 0)
putchar('0');
int ans[1 << 5], top = 0;
while(x)
ans[top ++] = x % 10, x /= 10;
for(; top; top --)
putchar(ans[top - 1] + '0');
putchar('\n');
}

const int N = 1 << 17, M = 1 << 17;

int n;

int head[N];
int top;

struct edge
{
int v, w, next;
}G[N << 1];

inline void addEdge(int u, int v, int w)
{
G[top].v = v, G[top].w = w, G[top].next = head[u];
head[u] = top ++;
}

struct data
{
int u, dis;
}st[N][17];

int dep[N];
int disToRoot[N];

void dfs(int u, int pre, int w)
{
st[u][0].u = pre;
st[u][0].dis = w;
dep[u] = dep[pre] + 1;
disToRoot[u] = disToRoot[pre] + w;

for(int i = head[u]; ~ i; i = G[i].next)
if(G[i].v != pre)
dfs(G[i].v, u, G[i].w);
}

inline void getSt()
{
for(int i = 1; i < 17; i ++)
for(int j = 1; j <= n; j ++)
st[j][i].u = st[st[j][i - 1].u][i - 1].u,
st[j][i].dis = st[j][i - 1].dis + st[st[j][i - 1].u][i - 1].dis;
}

struct query
{
int id, s, t, p;

inline friend int operator <(query a, query b)
{
return a.p < b.p;
}
}a[M];

int getLca(int u, int v)
{
if(dep[u] < dep[v])
swap(u, v);

for(int i = 17 - 1; ~ i; i --)
if(dep[u] - (1 << i) >= dep[v])
u = st[u][i].u;

if(u == v)
return u;

for(int i = 17 - 1; ~ i; i --)
if(st[u][i].u != st[v][i].u)
u = st[u][i].u, v = st[v][i].u;

return st[u][0].u;
}

inline int climb(int &u, int lca, int p)
{
int ret = 0;

while(1)
{
if(disToRoot[u] - disToRoot[lca] < p)
break;

int left = p;

for(int i = 17 - 1; ~ i; i --)
if(left >= st[u][i].dis)
left -= st[u][i].dis, u = st[u][i].u;

ret ++;
}

return ret;
}

int ans[M];

int f[N][17];

inline int jump(int &u, int lca)
{
int ret = 0;

for(int i = 17 - 1; ~ i; i --)
if(dep[f[u][i]] > dep[lca])
ret += 1 << i, u = f[u][i];

return ret;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("childrenTrip.in", "r", stdin);
freopen("childrenTrip.out", "w", stdout);
#endif

n = read();
memset(head, - 1, sizeof(head));
top = 0;

for(int i = 1; i < n; i ++)
{
int u = read(), v = read(), w = read();
addEdge(u, v, w), addEdge(v, u, w);
}

dep[1] = - 1;
disToRoot[1] = 0;
dfs(1, 1, 0);
getSt();

int m = read();

for(int i = 0; i < m; i ++)
a[i].id = i, a[i].s = read(), a[i].t = read(), a[i].p = read();

sort(a, a + m);
int p;

for(p = 0; p < m; p ++)
if(a[p].p > (int)sqrt(n))
break;

for(int i = p; i < m; i ++)
{
int lca = getLca(a[i].s, a[i].t);
ans[a[i].id] = climb(a[i].s, lca, a[i].p) + climb(a[i].t, lca, a[i].p)
+ (disToRoot[a[i].s] + disToRoot[a[i].t] - 2 * disToRoot[lca] + a[i].p - 1) / a[i].p;
}

for(int i = 1; i <= n; i ++)
f[i][0] = i;

int last = 0;

for(int i = 0; i < p; i ++)
{
if(a[i].p != last)
{
for(int j = 1; j <= n; j ++)
{
int rest = a[i].p - (disToRoot[j] - disToRoot[f[j][0]]);
int u = f[j][0];

for(; ;)
{
rest -= st[u][0].dis;
u = st[u][0].u;

if(rest >= 0)
f[j][0] = u;

if(rest <= 0 || ! dep[u])
break;
}
}

for(int j = 1; j < 17; j ++)
for(int k = 1; k <= n; k ++)
f[k][j] = f[f[k][j - 1]][j - 1];

last = a[i].p;
}

int lca = getLca(a[i].s, a[i].t);

ans[a[i].id] = jump(a[i].s, lca) + jump(a[i].t, lca)
+ (disToRoot[a[i].s] + disToRoot[a[i].t] - 2 * disToRoot[lca] + a[i].p - 1) / a[i].p;
}

for(int i = 0; i < m; i ++)
println(ans[i]);
}
```\]