Untitled diff
15 removals
136 lines
7 additions
128 lines
#include <bits/stdc++.h>
#include <bits/stdc++.h>
using namespace std;
using namespace std;
#define error(args...) { vector<string> _v = split(#args, ','); err(_v.begin(), args); }
#define error(args...) { vector<string> _v = split(#args, ','); err(_v.begin(), args); }
vector<string> split(const string& s, char c) { vector<string> v; stringstream ss(s); string x; while (getline(ss, x, c)) v.push_back(move(x)); return v; }
vector<string> split(const string& s, char c) { vector<string> v; stringstream ss(s); string x; while (getline(ss, x, c)) v.push_back(move(x)); return v; }
void err(vector<string>::iterator it) {}
void err(vector<string>::iterator it) {}
template<typename T, typename... Args> void err(vector<string>::iterator it, T a, Args... args) { cerr << it->substr((*it)[0] == ' ', it->length()) << " = " << a << '\n'; err(++it, args...); }
template<typename T, typename... Args> void err(vector<string>::iterator it, T a, Args... args) { cerr << it->substr((*it)[0] == ' ', it->length()) << " = " << a << '\n'; err(++it, args...); }
#define MAXN 100013
#define MAXN 100013
#define MAXM 100013
#define MAXM 100013
#define MAXC 100013
#define MAXC 100013
#define MAXSQRT 320
#define MAXSQRT 320
int N, M;
int N, M;
int C[MAXN];
int C[MAXN];
vector<int> adj[MAXN];
vector<int> adj[MAXN];
int preorder[MAXN]; // where a node appears in preorder
int preorder[MAXN]; // where a node appears in preorder
int ID[MAXN]; // real value of a preorder index
int ID[MAXN]; // real value of a preorder index
int endofsubtree[MAXN]; // last element in preorder of subtree of this node
int endofsubtree[MAXN]; // last element in preorder of subtree of this node
int t = 0;
int t = 0;
int BL[MAXN];
int BL[MAXN];
struct query {
struct query {
int id, b, e, k;
int id, b, e, k;
bool operator<(query other) {
bool operator<(query other) {
return BL[b] == BL[other.b] ? e < other.e : BL[b] < BL[other.b];
return BL[b] == BL[other.b] ? e < other.e : BL[b] < BL[other.b];
}
}
} Q[MAXM];
} Q[MAXM];
int VAL[MAXN]; // mo stuff
int VAL[MAXN]; // mo stuff
bool VIS[MAXN];
int ANS[MAXM];
int ANS[MAXM];
struct fenwick {
struct fenwick {
int ar[MAXC] = {0};
int ar[MAXC] = {0};
int query(int idx) {
int query(int idx) {
int ans = 0;
int ans = 0;
for (int i = idx + 1; i > 0; i -= i & -i) {
for (int i = idx + 1; i > 0; i -= i & -i) {
ans += ar[i];
ans += ar[i];
}
}
return ans;
return ans;
}
}
void update(int idx, int x) {
void update(int idx, int x) {
for (int i = idx + 1; i < MAXC; i += i & -i) {
for (int i = idx + 1; i < MAXC; i += i & -i) {
ar[i] += x;
ar[i] += x;
}
}
}
}
} F;
} F;
void dfs(int n, int prev=-1) {
void dfs(int n, int prev=-1) {
preorder[n] = t++;
preorder[n] = t++;
ID[preorder[n]] = n;
ID[preorder[n]] = n;
for (int x : adj[n]) {
for (int x : adj[n]) {
if (x != prev) {
if (x != prev) {
dfs(x, n);
dfs(x, n);
}
}
}
}
endofsubtree[n] = t - 1;
endofsubtree[n] = t - 1;
}
}
inline void check(int x) {
inline void check(int x, int p) {
int prev = VAL[C[x]];
F.update(VAL[C[x]], -1);
if (VIS[x]) {
VAL[C[x]] += p;
VAL[C[x]]--;
}
else {
VAL[C[x]]++;
}
VIS[x] ^= 1;
F.update(prev, -1);
F.update(VAL[C[x]], 1);
F.update(VAL[C[x]], 1);
}
}
void compute() {
void compute() {
int curB = Q[0].b, curE = Q[0].b - 1;
int curB = Q[0].b, curE = Q[0].b - 1;
for (int i = 0; i < M; i++) {
for (int i = 0; i < M; i++) {
query q = Q[i];
query q = Q[i];
// error(q.id, q.b, q.e);
// error(q.id, q.b, q.e);
while (curB > q.b) check(ID[--curB]);
while (curB > q.b) check(ID[--curB], 1);
while (curB < q.b) check(ID[curB++]);
while (curB < q.b) check(ID[curB++], -1);
while (curE > q.e) check(ID[curE--]);
while (curE > q.e) check(ID[curE--], -1);
while (curE < q.e) check(ID[++curE]);
while (curE < q.e) check(ID[++curE], 1);
ANS[q.id] = F.query(MAXC - 1) - F.query(q.k - 1);
ANS[q.id] = F.query(MAXC - 1) - F.query(q.k - 1);
}
}
}
}
int main() {
int main() {
ios_base::sync_with_stdio(false);
ios_base::sync_with_stdio(false);
cin.tie(0);
cin.tie(0);
// freopen("input.txt", "r", stdin);
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// freopen("output.txt", "w", stdout);
cin >> N >> M;
cin >> N >> M;
for (int i = 0; i < N; i++) {
for (int i = 0; i < N; i++) {
cin >> C[i];
cin >> C[i];
}
}
// okee read in the edges
// okee read in the edges
for (int i = 0; i < N - 1; i++) {
for (int i = 0; i < N - 1; i++) {
int a, b;
int a, b;
cin >> a >> b;
cin >> a >> b;
a--; b--;
a--; b--;
adj[a].push_back(b);
adj[a].push_back(b);
adj[b].push_back(a);
adj[b].push_back(a);
}
}
dfs(0);
dfs(0);
int size = sqrt(N);
int size = sqrt(N);
for (int i = 0; i < N; i++) {
for (int i = 0; i < N; i++) {
BL[i] = i / size;
BL[i] = i / size;
}
}
for (int i = 0; i < M; i++) {
for (int i = 0; i < M; i++) {
int v, k;
int v, k;
cin >> v >> k; v--;
cin >> v >> k; v--;
Q[i].id = i;
Q[i].id = i;
Q[i].b = preorder[v];
Q[i].b = preorder[v];
Q[i].e = endofsubtree[v];
Q[i].e = endofsubtree[v];
Q[i].k = k;
Q[i].k = k;
}
}
sort(Q, Q + M);
sort(Q, Q + M);
compute();
compute();
for (int i = 0; i < M; i++) {
for (int i = 0; i < M; i++) {
cout << ANS[i] << '\n';
cout << ANS[i] << '\n';
}
}
cout.flush();
cout.flush();
return 0;
return 0;
}
}