$$$2800$$$

dsu, maths, constructive

When $$$N$$$ is odd, it is always impossible.

Proving it might be an inspiration at some situations. It is highly recommended that readers can prove it themselves.

The proof of this is also at the end of the blog.

Print out the all possible next nodes, does some nodes have the same next nodes?

From hint 2, we can notice that node $$$i$$$ and node $$$i + \frac {N} {2}$$$ is actually the same. So, we can simply set $$$i$$$ goes to $$$(2*i)$$$ $$$mod$$$ $$$N$$$ and $$$i + \frac {N} {2}$$$ goes to $$$(2 * i + 1)$$$ $$$mod$$$ $$$N$$$.

Then we can magically notice that these nodes will form cycles. Hence, our task now is to merge the cycles into one (because we want all nodes to be in a cycle).

Imagine now we have two cycles: $$$C1$$$ and $$$C2$$$. $$$C1$$$ contains $$$i \rightarrow (2 * i)$$$ $$$mod$$$ $$$N$$$ and $$$C2$$$ contains $$$i + \frac {N} {2} \rightarrow (2 * i + 1)$$$ $$$mod$$$ $$$N$$$.

By crossing the edges, we can see that the cycles are merged! Hence, in order to merge two cycles, we can simply swap the next steps of $$$i$$$ and $$$i+\frac {N} {2}$$$.

In order to maintain cycles, we can use a dsu to maintain whether two nodes are already in the same cycle.

We will prove that when $$$N$$$ is odd, it is impossible to build a path by looking at $$$\frac {N - 1} {2}$$$.

What goes to $$$0$$$ is either $$$0$$$ or $$$\frac {N - 1} {2}$$$. Since if we started from $$$0$$$ and ends at $$$0$$$ immediately, it cannot be the answer. Thus, the next step of $$$\frac {N - 1} {2}$$$ must be $$$0$$$.

What goes to $$$N - 1$$$ is either from $$$(N - 1)$$$ or $$$\frac {N - 1} {2}$$$. Similarly, the next step of $$$\frac {N - 1} {2}$$$ must be $$$N - 1$$$.

Since the next step of $$$\frac {N - 1} {2}$$$ can only be one of $$$0$$$ or $$$N - 1$$$, it is impossible to build the path.

$$$*2700$$$ and some unique ideas used.

Data structures, sqrt decomposition

sqrt decomposition

Let $$$next_{i} =$$$ index to the next block, how to we exploit this?

Jump until you can't then find the last index you can jump to that belongs to the same block.

Let us jump until we are out of the box, then we record $$$jumps_{i} =$$$ jumps needed and $$$next_{i} =$$$ index to the next block.

We will separate the queries and the modifications.

It can also be solved using splay tree but I wrote this blog to share this technique!

I didn't expect it to be sqrt decomposition, what a nice example for sqrt decomposition.

$$$*2600$$$ but I personally think it's $$$*2300$$$ to $$$*2500$$$

Multisource BFS and simple BFS

Does placing a block in an empty cell matter?

Nope, it doesn't matter.

This task is simple, since blocking every cell is the optimal solution.

This is because it cannot escape anyway so just cover everything.

Max number of block placed $$$=$$$ Total number of '.' $$$-$$$ Min blocks needed to move to an exit.

This task is also relatively simple, since Max number of block placed $$$=$$$ Min blocks needed to move to an exit. We can simply find the shortest path from $$$V$$$ to the only exit and just cover the other unused blocks.

This can be done easily using a $$$BFS$$$ and check minimum distance to every reachable exit.

It is easy to observe that we don't need all exits, taking more than that is simply using up more spaces. We only need 2.

Maybe we consider moving to a cell $$$(i,j)$$$ first then we split into 2 paths going to 2 exits?

This is task is what makes the problem hard.

We notice that we can always consider moving to a cell $$$(i,j)$$$ first then then we split into 2 paths going to 2 exits.

So our path would be $$$V \rightarrow (i,j) \rightarrow A,B$$$ where $$$A$$$ and $$$B$$$ are the closest exits. So no of cells used $$$=$$$ $$$dis(V,(i,j)) + dis((i,j),A) + dis((i,j),B)$$$. In order to minimize this cells used, and the first $$$dis(V,(i,j))$$$ is constant, we should minimize the last $$$dis((i,j),A) + dis((i,j),B)$$$. This is sum of distances of the closest two exits.

So, we need to find two closest exits to a cell and that can be performed using a multisource $$$BFS$$$. Also note that we also have to make sure the same exit isn't recorded twice. That inspires us to let $$$who_{x,y,0/1} = $$$ id of exit. The rest is just implementation.

Note: make sure to set who is going to a cell before throwing it into the queue, or else you would get MLE like me.

Amazing problem, somehow looks familiar for me.

Anyways, I had the idea of converting the grid into a graph with $$$N*M$$$ nodes and adding an edge of where it came from in the $$$BFS$$$ from $$$V$$$. Then convert the graph to $$$DAG$$$ then we can perform $$$DP$$$ on the $$$DAG$$$. Then I noticed that it is quite hard to do so, while I'm currently still doubting it'll work or not.

It is rather implementation heavy for me so even though I had the idea from like the beginning, I needed many submissions to pass.

$$$#.#.#$$$

$$$.#.#.$$$

$$$#.#.#$$$

$$$.#.#.$$$

$$$#.#.#$$$

Maybe try going in powers of 2 and check if it is still a black cell?

Binary search on the range $$$[C,2 * C)$$$?

Notice that if we add a value $$$k$$$ to $$$(x,y)$$$ to form $$$(x+k,y)$$$. (Asumming that we go to the right)

We can't just directly binary search $$$k$$$ because it might go to another grid to the right.

Ok, let us jump in powers of 2. Notice that if current power of two is still in the block and the next power is not in the block.

Let current power of 2 = $$$C$$$, and the next power = $$$2*C$$$;

This is because $$$(x+C, y)$$$ will still be in the block, this means that $$$M<C$$$, then after we find such C such that $$$(x+C, y)$$$ is black and $$$(x+2*C,y)$$$ is white. With this we can binary search the breakpoint.

We can find $$$M$$$ and other are just implementation.

HLD/binary lifting for finding LCA, dfs, virtual tree

Does every node from $$$1$$$ to $$$N$$$ matter in a query?

Definitely not all nodes matter. Only the $$$LCA$$$ of nodes in $$${a}$$$ and the nodes in $$${a}$$$ matters.

This completely satisfies the condition of building virtual trees.

If we traverse through the nodes from the root in the virtual tree, there will be three conditions:

1) If we are at a non-red node and we have $$$\geq 2$$$ children that is red?

2) If we are at a non-red node and we have only $$$1$$$ child that is red?

3) If we are at a red node?

Let us build a virtual tree based on the nodes. There are many blogs that show how to do this. If you need a template of building a virtual tree, you can DM me for it.

Let us DFS from the root of the virtual tree.

1) If we are at a non-red node and we have $$$\geq 2$$$ children that is red? This means that we should just break the node here.

2) If we are at a non-red node and we have only $$$1$$$ child that is red? We can simply color current node red.

3) If we are at a red node? From the second condition, we can simply count the number of children that are red and add it to the answer.

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;

const int _N = 2e5;
vector<int> G[_N];
namespace shupou {
    int dfn[_N], tim = 0, dep[_N], sz[_N], fa[_N], top[_N], son[_N];
    void dfs_heavy(int u, int f) {
        dfn[u] = ++tim; sz[u] = 1; fa[u] = f; dep[u] = dep[f] + 1;
        for (auto& v : G[u]) {
            if (v == f) continue;
            dfs_heavy(v, u);
            sz[u] += sz[v];
            if (sz[v] > sz[son[u]]) son[u] = v;
        }
    }
    void dfs_top(int u, int f) {
        top[u] = f;
        if (son[u]) dfs_top(son[u], f);
        for (auto& v : G[u]) {
            if (v == fa[u] || v == son[u]) continue;
            dfs_top(v, v);
        }
    }
    int lca(int x, int y) {
        while (top[x] != top[y]) {
            if (dep[top[x]] >= dep[top[y]]) x = fa[top[x]];
            else y = fa[top[y]];
        }
        return dep[x] < dep[y] ? x : y;
    }
    void shupou(int root = 1) {
        dfs_heavy(root, 0);
        dfs_top(root, root);
    }
};
namespace xushu {
    int a[_N], pt = 0, npt = 0;
    vector<int> XG[_N], prev;
    int cmp(int x, int y) { return shupou::dfn[x] < shupou::dfn[y]; }
    void build(vector<int>& x) {
        pt = 0;
        for (auto& v : x) a[++pt] = v;
        sort(a + 1, a + pt + 1, cmp);
        npt = pt;
        for (int i = 2; i <= pt; i++) {
            int lca = shupou::lca(a[i], a[i - 1]);
            if (lca != a[i] && lca != a[i - 1]) a[++npt] = lca;
        }
        sort(a + 1, a + npt + 1);
        npt = unique(a + 1, a + npt + 1) - (a + 1);
        sort(a + 1, a + npt + 1, cmp);
        prev.push_back(a[1]);
        for (int i = 2; i <= npt; i++) {
            int lca = shupou::lca(a[i], a[i - 1]);
            XG[lca].push_back(a[i]);
            prev.push_back(a[i]);
        }
    }
    void clear() {
        for (auto& v : prev) XG[v].clear();
        prev.clear();
        pt = 0; npt = 0;
    }
};
bool red[_N];
int dfs(int u) {
    int ans = 0;
    for (auto& v : xushu::XG[u]) ans += dfs(v);
    if (red[u]) {
        for (auto& v : xushu::XG[u])
            if (red[v]) ans++;
    }
    else {
        int cnt = 0;
        for (auto& v : xushu::XG[u])//if current = not important city
            if (red[v]) cnt++;
        if (cnt > 1) ans++;//if we have >= 2 cities meaning we must break here
        if (cnt == 1) red[u] = true; //or else just make it red and just go up
    }
    return ans;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int N; cin >> N;
    for (int i = 1; i <= N - 1; i++) {
        int u, v; cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    shupou::shupou();
    int Q; cin >> Q;
    while (Q--) {
        int M; cin >> M;
        vector<int> p(M);
        bool neighbour = false;
        for (int i = 0; i < M; i++) {
            cin >> p[i];
            red[p[i]] = true;
        }
        for (int i = 0; i < M; i++) 
            if (red[shupou::fa[p[i]]] == true)//if its father is red and current node is also red, it can never be colored
                neighbour = true;

        if (neighbour) { //if it is impossible to disconnect them
            cout << "-1\n";
            for (int i = 0; i < M; i++) red[p[i]] = false;
            continue;
        }
        else {
            xushu::build(p); //build the virtual tree
            cout << dfs(xushu::a[1]) << '\n'; //dfs from root of the virtual tree
            for (auto& x : xushu::prev) red[x] = false; //reset all to without color
            xushu::clear(); //clear the virtual tree
        }
    }
}

I've first heard about virtual trees around 3/4 months ago during a camp for preparation of IOI 2023. This the first problem I've seen that is solved using virtual tree. Amazing problem (also introduction to virtual trees), but I used 4/5 hours on solving 1 problem only. It took me too long to implement virtual tree. Also, I think the problem rating is rated too high, maybe because virtual tree is not well known back then.

Binary search, greedy, dfs

Let us binary search on number of operations done. If we design a check function for "Can we do $$$x$$$ moves? It must satisfy a $$$true, ..., true, false, ..., false$$$ scenario. So we can determine the number of moves that each node must move, how to check if it is moving it around possible?

Greedy algorithm used:

Find the maximum number of steps it can move down with, if it can be moved down $$$X$$$ steps, move down. If there is no way to move $$$X$$$ steps down, move up and consider it later.

When would this algorithm stop? It is when some of our nodes are unable to move down and up. This is because when we use a dfs, it ensures that every subtree below it has already satisfied the conditions, we only need to consider current node.

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;

void solve() {
	int N; cin >> N;
	vector<vector<int>> g(N + 1);
	for (int i = 0; i < N - 1; i++) {
		int u, v; cin >> u >> v;
		g[u].push_back(v); g[v].push_back(u);
	}
	int K; cin >> K;
	vector<int> step(N + 1), f(N + 1), col(N + 1), t(K + 1);
	for (int i = 1; i <= K; i++)
		cin >> t[i];

	function<bool(int, int)> dfs = [&](int u, int fa) {
		for (auto& v : g[u]) {
			if (v == fa) continue; //don't go back up first
			if (dfs(v, u) == 0) return 0;//if some node cannot work return false
			if (!col[v]) f[u] = max(f[u], f[v] + 1); //if it is white, f[u]=max(f[u],f[v]+1) because we can use one more operation done
			//just record maximum
		}
		if (step[u] <= f[u]) {//if we can move down, just move down
			step[u] = 0;//remove that node's steps 
			return 1; //return possible
		}
		if (fa == 0 || col[fa]) return 0; //since my code roots at 1, I set its father to be 0
		//if my father is already colored black or it is the root, return false
		step[fa] = step[u] - 1; step[u] = 0; col[fa] = 1;//or else move up, now your steps would - 1
		return 1;
	};

	auto check = [&](int x) {
		for (int i = 0; i <= N; i++) f[i] = step[i] = col[i] = 0; //clear everything
		for (int i = 1; i <= K; i++) {
			int u = t[i];
			step[u] = (x / K);
			if (i <= x % K) step[u]++;//counting step[i] for each a[i]
			col[u] = 1;
		}
		return dfs(1, 0);
	};
	int l = 0, r = N, ans = -1;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (check(mid)) { 
			ans = mid; 
			l = mid + 1;
		}
		else {
			r = mid - 1;
		}
	}
	cout << ans << '\n';
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	int T; cin >> T;
	while (T--) {
		solve();
	}
}

Interesting problem with a very cool implementation.

Binary search, standard 2-SAT, segment tree

There are many blogs about 2-SAT (and Tarjan). Read the next paragraph if you are like me and don't get how to build the graph. You can search up the internet for it.

A good blog in Chinese: link. I read like 4-5 blogs and websites to learn about it but still don't get how the graph is built. The blog provides an excellent description, "A directed edge from A to B means that if we choose A then we must choose B, but when we choose B, we don't necessary choose A."

Lets get back to the problem. A wise man once said: "When you see a problem that maximize minimum ... or minimize maximum ... , it's highly likely that it is binary search."

By observation this problem has a : $$$true, ..., true, false, ..., false$$$ scenario if we choose a function to check if $$$min \geq k$$$. I think this is quite easy to find out this pattern. If you can't see this pattern, try learning binary search from Um_nik first XD.

Now we need to write a check function to check if the graph satisfies a value $$$k$$$ to have $$$min$$$ $$$\geq$$$ $$$k?$$$

From here onwards we will let $$$A$$$ $$$=$$$ we choose node $$$A$$$, $$$A'$$$ $$$=$$$ we don't choose A.

Then, we can observe that we have 2 cases:

We notice that the bottleneck of this solution would be on the $$$2nd$$$ case. What should we do to optimize it? What if we took ranges to represent them into nodes? Then, what is the trick to make as few ranges we can? Then we can notice that we can use ranges in segment tree to represent a node!

Ok, let us define $$$tr_{L,R}$$$ to be the node that represents range $$$[L,R]$$$.

Let us redo $$$2nd$$$ case. We need to build an edge from $$$i$$$ -> $$$tr_{i-k+1,i-1}'$$$ and $$$i$$$ -> $$$tr_{i+1,i+k-1}'$$$. We also need to add edges from $$$tr_{L,R}$$$, $$$tr_{L,R}'$$$ -> $$$tr_{L, mid}'$$$ and $$$tr_{L,R}'$$$ -> $$$tr_{mid+1, R}'$$$. This is because if we don't want to take $$$[L,R]$$$, we also must not take $$$[L, mid]$$$ and $$$[mid+1, R]$$$. If $$$tr'_{i, i}$$$ is satisfied, we must not take $$$i'$$$, meaning we also need to add edge from every $$$tr'_{i, i}$$$ to $$$i'$$$.

After we did this, just run tarjan and compute all SCCs. If an $$$i$$$ and $$$i'$$$ belongs to the same SCC, answer will be NO because it's impossible to take $$$i$$$ and not take $$$i$$$ at the same time.

Otherwise, the answer is YES.

//闲敲棋子落灯花//
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
 
const int NN = 6e5 + 500;
stack<int> s;
int dfn[NN], low[NN], timer, cnt, col[NN];
bool vis[NN];
vector<int> G[NN];
vector<int> Neo[NN];
void tarjan(int u) {
    vis[u] = true;
    low[u] = dfn[u] = ++timer;
    s.push(u);
    for (auto v : Neo[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if (vis[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (low[u] == dfn[u]) {
        cnt++;
        while (1) {
            int x = s.top(); s.pop();
            vis[x] = false;
            col[x] = cnt;
            if (x == u) break;
        }
    }
}
 
int N, M;
void add_edge(int x, int y) {
    Neo[x].push_back(y);
    return;
}
void build(int p, int l, int r) {
    if (l == r) {
        add_edge(p + 2 * N, l + N);
        return;
    }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    add_edge(p + 2 * N, (p << 1) + 2 * N);
    add_edge(p + 2 * N, (p << 1 | 1) + 2 * N);
    return;
}
void add(int p, int l, int r, int ql, int qr, int x) {
    if (ql <= l && r <= qr) {
        add_edge(x, p + 2 * N);
        return;
    }
    int mid = (l + r) >> 1;
    if (ql <= mid) add(p << 1, l, mid, ql, qr, x);
    if (qr >= mid + 1) add(p << 1 | 1, mid + 1, r, ql, qr, x);
    return;
}
bool check(int k) {
    if (k == 1) return true;
    for (int i = 0; i <= 2 * N; i++)
        Neo[i].clear();
    for (int i = 1; i <= N; i++)
        for (auto& v : G[i])
            add_edge(i + N, v);
 
    for (int i = 1; i <= N; i++) {
        int L = max(1, i - k + 1), R = i - 1;
        if (L <= R) add(1, 1, N, L, R, i);
        L = i + 1; R = min(N, i + k - 1);
        if (L <= R) add(1, 1, N, L, R, i);
    }
    while (s.size()) s.pop();
    timer = 0, cnt = 0;
    for (int i = 1; i <= 6 * N; i++)
        low[i] = dfn[i] = vis[i] = 0;
 
    for (int i = 1; i <= 6 * N; i++)
        if (!dfn[i])
            tarjan(i);
 
    for (int i = 1; i <= N; i++)
        if (col[i] == col[i + N])
            return false;
    return true;
}
void solve() {
    cin >> N >> M;
    for (int i = 0; i <= 6 * N; i++) {
        G[i].clear();
        Neo[i].clear();
    }
    for (int i = 0; i < M; i++) {
        int u, v; cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    build(1, 1, N);
    int l = 1, r = N;
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    cout << l << '\n';
    return;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
 
    int T; cin >> T;
    while (T--) {
        solve();
    }
}

This is the first time I saw a 2-SAT problem. Bruh I literally spent 1.5 hours to just to read on 2-SAT. But the problem is amazing and interesting. Mixture of ideas (2-SAT, binary search and segment tree) was insane. Also, I submitted like 7 times like a dumbass before ACing.

We can represent $$$i'$$$ as node with index $$$i + N$$$, also $$$tr_{L,R}$$$ with index $$$p$$$ in the segment tree with node with index $$$p+2*N$$$ for simpler implementation. Remember to clear all edges and the edges created from the previous check function (got like 4 WAs for this). At the same time, we also need to make sure that the indexes will not be $$$\leq 0$$$ or $$$\geq N+1$$$ when connecting $$$i$$$ to $$$[i-k+1,i-1]$$$ and $$$[i+1,i+k-1]$$$.

First of all, we can observe that queries can be done offline and the only thing that matters for each query is the color.

Lets do each color one by one, we can observe that distance between two nodes in the query = original distance $$$-$$$ sum of edge weight of color $$$x$$$ + number of edges that have color $$$x$$$ in the path * new weight length.

Now let us try to find what can be done. We can see that the number of edges with color $$$x$$$ going out of subtree $$$u$$$ will $$$+1$$$ if the starting point is from subtree $$$u$$$. So we can just $$$+1$$$ to all nodes inside subtree $$$u$$$. Then we can see that number of edges from node $$$x$$$ to $$$y$$$. Similarly, we can do $$$+W$$$ for weight sum.

Distance in original graph can be found in $$$O(N log N)$$$ using binary lifting and a dfs function. Simultaneously, since we need to add $$$+1$$$ to each node one by one, we will need to do $$$O(N ^ 2)$$$ to do all necessary operations.

We can try finding a better way to do the $$$+1$$$ and $$$+W$$$ operations. Well, if you have learnt dfn, you should be able to solve the problem from here. If we represent $$$tin_{ i }$$$ be the time we entered subtree $$$i$$$ and $$$tout_{ i }$$$ we left subtree $$$i$$$. Then we can use this to observe that we need to do $$$+val$$$ in a range and find a value at a point. What do we need to have if we want to do these operations fast? Yes, segment tree!

However, we cannot just declare a new segment tree each time. We need to reuse the segment tree. So, we'll have to do $$$-1$$$ and $$$-W$$$ operations to revert the segment tree, or do something like range set.

// LUOGU_RID: 139270322
// Problem: F - Colorful Tree
// Memory Limit: 1024 MB
// Time Limit: 4000 ms

//闲敲棋子落灯花//
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;

struct edge {
    int u, v, color, w;
};
struct query {
    int u, v, color, new_w, id;
};
const int N = 1e5 + 50, K = 30;
vector<pair<int, int>> G[N];
int dep[N], sp[N][K], val[N], ti, tin[N], tout[N];
void dfs(int u, int p) {
    tin[u] = ++ti; dep[u] = dep[p] + 1; sp[u][0] = p;
    for (int i = 1; i < K; i++)sp[u][i] = sp[sp[u][i - 1]][i - 1];
    for (auto v : G[u]) if (v.first != p) {
        val[v.first] = val[u] + v.second;
        dfs(v.first, u);
    }
    tout[u] = ti;
}
int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int i = K - 1; i >= 0; i--)if (dep[sp[u][i]] >= dep[v])u = sp[u][i];
    if (u == v) return u;
    for (int i = K - 1; i >= 0; i--)if (sp[u][i] != sp[v][i])u = sp[u][i], v = sp[v][i];
    return sp[v][0];
}
int dis(int u, int v) {
    int l = lca(u, v);
    return val[u] + val[v] - 2 * val[l];
}
struct segtree {
    struct node {
        i64 v;
        friend node operator + (node a, node b) {
            node t; t.v = a.v + b.v;
            return t;
        }
    };
    vector<node> tr;
    vector<int> tag;
    int SZ = 0;
    void apply_node(int p, int x) {
        tr[p].v += x;
        tag[p] += x;
    }
    void pushdown(int p) {
        if (tag[p] != 0) {
            apply_node(p << 1, tag[p]);
            apply_node(p << 1 | 1, tag[p]);
            tag[p] = 0;
        }
        return;
    }

    segtree(int N) {
        SZ = N + 200;
        tr.resize(SZ * 4);
        tag.assign(SZ * 4, 0);
    }
#define ls p<<1
#define rs p<<1|1
    void update(int x, int v) { update(1, 1, SZ - 100, v, x, x); }
    void update(int x, int y, int v) { update(1, 1, SZ - 100, v, x, y); }
    void update(int p, int l, int r, int v, int lq, int rq) {
        //cout << "update: " << p << ' ' << l << ' ' << r << ' ' << lq << ' ' << rq << '\n';
        if (lq <= l && r <= rq) {
            apply_node(p, v);
            return;
        }
        int mid = (l + r) >> 1;
        pushdown(p);
        if (lq <= mid) update(ls, l, mid, v, lq, rq);
        if (rq >= mid + 1) update(rs, mid + 1, r, v, lq, rq);
        tr[p] = tr[ls] + tr[rs];
    }
    node query(int x) { return query(1, 1, SZ - 100, x, x); }
    node query(int x, int y) { return query(1, 1, SZ - 100, x, y); }
    node query(int p, int l, int r, int lq, int rq) {
        //cout << "query: " << p << ' ' << l << ' ' << r << ' ' << lq << ' ' << rq << '\n';
        if (lq <= l && r <= rq) {
            return tr[p];
        }
        int mid = (l + r) >> 1;
        pushdown(p);
        if (lq <= mid && rq >= mid + 1) return query(ls, l, mid, lq, rq) + query(rs, mid + 1, r, lq, rq);
        if (lq <= mid) return query(ls, l, mid, lq, rq);
        if (rq >= mid + 1) return query(rs, mid + 1, r, lq, rq);
    }
};
//update/query -> point or range
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int N, Q; cin >> N >> Q;
    vector<vector<edge>> C(N + 1);
    for (int i = 0; i < N - 1; i++) {
        int a, b, c, d; cin >> a >> b >> c >> d;
        G[a].push_back({ b,d });
        G[b].push_back({ a,d });
        C[c].push_back({ a,b,c,d });
    }
    dfs(1, 0);
    vector<vector<query>> Qp(N + 1);
    vector<int> ans(Q + 1);
    for (int i = 0; i < Q; i++) {
        int a, b, c, d; cin >> a >> b >> c >> d;
        ans[i] = dis(c, d);
        Qp[a].push_back({ c,d,a,b,i });
    }
    /*
        let the initial answer for each query to be
        l = lca(u,v), ans[i] = dis(u,l) + dis(l,v)
        loop through each color:
            add the entire subtree  S       +1 when going down
                                    dep     +w when going down
            then ans[i] -= dis(a,b) on the subtree
                 ans[i] += S(a,b) * new_w

        this is O(N * C) where C = color count
        we cant just traverse every single node so lets use
        dfn values and a segment tree
    */
    segtree segcnt(N), segval(N);
    for (int i = 1; i <= N; i++) {
        for (auto p : C[i]) {
            int u = p.u, v = p.v, w = p.w;
            if (dep[u] > dep[v]) swap(u, v);
            segcnt.update(tin[v], tout[v], 1);
            segval.update(tin[v], tout[v], w);
        }

        for (auto p : Qp[i]) {
            int u = p.u, v = p.v, w = p.new_w;
            if (dep[u] > dep[v]) swap(u, v);
            int l = lca(u, v);
            int cnt = segcnt.query(tin[u]).v + segcnt.query(tin[v]).v - 2 * segcnt.query(tin[l]).v;
            int val = segval.query(tin[u]).v + segval.query(tin[v]).v - 2 * segval.query(tin[l]).v;
            ans[p.id] -= val;
            ans[p.id] += cnt * p.new_w;
        }

        for (auto p : C[i]) {
            int u = p.u, v = p.v, w = p.w;
            if (dep[u] > dep[v]) swap(u, v);
            segcnt.update(tin[v], tout[v], -1);
            segval.update(tin[v], tout[v], -w);
        }
    }
    for (int i = 0; i < Q; i++) {
        cout << ans[i] << '\n';
    }
}

Using the trick $$$F_{L} - F_{L-1}$$$ to allow us to just max size $$$\leq L$$$. Then we can calculate the DP with $$$dp_{i}=$$$ number of graphs that satisfy the condition with $$$i$$$ nodes. The cost is calculated using Prüfer sequences. Then we can just do something like knapsack with a $$$O(N * L)$$$ precomputed costs. So final time complexity is $$$O(N * L)$$$. For more information, read from the blog with the provided link above.