• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

# [做题记录] [Ynoi2011] 成都七中

4小时前 2次浏览

``````#include <bits/stdc++.h>
#include <bits/extc++.h>

using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;

class Input {
#define MX 1000000
private :
char buf[MX], *p1 = buf, *p2 = buf;
inline char gc() {
if(p1 == p2) p2 = (p1 = buf) + fread(buf, 1, MX, stdin);
return p1 == p2 ? EOF : *(p1 ++);
}
public :
Input() {
#ifdef Open_File
freopen("a.in", "r", stdin);
freopen("a.out", "w", stdout);
#endif
}
template <typename T>
inline Input& operator >>(T &x) {
x = 0; int f = 1; char a = gc();
for(; ! isdigit(a); a = gc()) if(a == '-') f = -1;
for(; isdigit(a); a = gc())
x = x * 10 + a - '0';
x *= f;
return *this;
}
inline Input& operator >>(char &ch) {
while(1) {
ch = gc();
if(ch != 'n' && ch != ' ') return *this;
}
}
inline Input& operator >>(char *s) {
int p = 0;
while(1) {
s[p] = gc();
if(s[p] == 'n' || s[p] == ' ' || s[p] == EOF) break;
p ++;
}
s[p] = '';
return *this;
}
#undef MX
} Fin;

class Output {
#define MX 1000000
private :
char ouf[MX], *p1 = ouf, *p2 = ouf;
char Of[105], *o1 = Of, *o2 = Of;
void flush() { fwrite(ouf, 1, p2 - p1, stdout); p2 = p1; }
inline void pc(char ch) {
* (p2 ++) = ch;
if(p2 == p1 + MX) flush();
}
public :
template <typename T>
inline Output& operator << (T n) {
if(n < 0) pc('-'), n = -n;
if(n == 0) pc('0');
while(n) *(o1 ++) = (n % 10) ^ 48, n /= 10;
while(o1 != o2) pc(* (--o1));
return *this;
}
inline Output & operator << (char ch) {
pc(ch); return *this;
}
inline Output & operator <<(const char *ch) {
const char *p = ch;
while( *p != '' ) pc(* p ++);
return * this;
}
~Output() { flush(); }
#undef MX
} Fout;

#define cin Fin
#define cout Fout
#define endl 'n'

using LL = long long;

inline int log2(unsigned int x);
inline int popcount(unsigned x);
inline int popcount(unsigned long long x);

const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;

int n, m;

struct BIT {
int c[N];
#define lowbit(x) (x & -x)
void upd(int x, int y) {
//x ++;
for(; x <= n; x += lowbit(x)) c[x] += y;
}
int qry(int x) {
int ans = 0;
for(; x; x -= lowbit(x)) ans += c[x];
return ans;
}
} bit;

struct edge {
int to, next;
} e[N << 1];

void push(int x, int y) {
}

int fa[N];
int all, rt, sz[N], vis[N];
void findrt(int x, int fx) {
sz[x] = 1;
int mx = 0;
for(int i = head[x]; i; i = e[i].next) {
int y = e[i].to;
if(y == fx || vis[y]) continue;
findrt(y, x);
sz[x] += sz[y];
mx = max(mx, sz[y]);
}
if(mx < all - sz[x]) mx = all - sz[x];
if(mx * 2 <= all || rt == 0) rt = x;
}

struct Qry {
int l, r, id;
Qry() {}
Qry(int _l, int _r, int _id) : l(_l), r(_r), id(_id) {}
} ;

vector<Qry> vec[N];
int bj[N];

void dfs(int x, int fx, int mnv, int mxv, vector<Qry> & ask, vector<Qry> &qry) {
for(Qry p : vec[x]) if(p.l <= mnv && mxv <= p.r && ! bj[p.id]) bj[p.id] = 1, qry.push_back(p);
for(int i = head[x]; i; i = e[i].next) {
int y = e[i].to;
if(vis[y] || y == fx) continue;
dfs(y, x, min(mnv, y), max(mxv, y), ask, qry);
}
}

int mx[N], Ans[N];

void calc(int x) {
dfs(x, 0, x, x, ask, qry);
sort(ask.begin(), ask.end(), [](Qry a, Qry b) { return a.r < b.r; } );
sort(qry.begin(), qry.end(), [](Qry a, Qry b) { return a.r < b.r; } );
for(int i = 0, j = 0; i < qry.size(); i ++) {
}
j ++;
}
Ans[qry[i].id] = bit.qry(n) - bit.qry(qry[i].l - 1);
}
if(mx[p.id]) bit.upd(mx[p.id], -1);
mx[p.id] = 0;
}
}

void solve(int x) {
vis[x] = 1;
//cerr << x << endl;
calc(x);
for(int i = head[x]; i; i = e[i].next) {
int y = e[i].to;
if(vis[y]) continue;
findrt(y, 0);
rt = 0; all = sz[y];
findrt(y, 0);
solve(rt);
}
}

int main() {
cin >> n >> m;
for(int i = 1; i <= n; i ++) cin >> co[i];
for(int i = 2, x, y; i <= n; i ++) {
cin >> x >> y;
push(x, y); push(y, x);
}
for(int i = 1; i <= m; i ++) {
int l, r, x;
cin >> l >> r >> x;
vec[x].push_back( Qry(l, r, i) );
}
all = n;
findrt(1, 0);
findrt(rt, 0);
solve(rt);
for(int i = 1; i <= m; i ++) cout << Ans[i] << endl;
return 0;
}

inline int log2(unsigned int x) { return __builtin_ffs(x); }
inline int popcount(unsigned int x) { return __builtin_popcount(x); }
inline int popcount(unsigned long long x) { return __builtin_popcountl(x); }

// Last Year
``````