void dfs(int v, int &k){
    used[v] = 1;
    int u, w;
    forn(i, sz(r[v])){
        u = r[v][i].ft;
        w = r[v][i].sc;
        if (!used[u])
            dfs(u, k);
        if (d1[v] + d2[u] + w == k){
            dp[v][0] += dp[u][0];
            dp[v][1] += dp[u][1];
        }
        else if (d1[v] + d2[u] + w == k + 1){
            dp[v][1] += dp[u][0];
            if (d1[u] + d2[u] == k + 1)
                dp[v][1] += dp[u][1];
        }
    }
}