Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Nguyen Huu Hoang Minh
- #include <bits/stdc++.h>
- #define sz(x) int(x.size())
- #define all(x) x.begin(),x.end()
- #define reset(x) memset(x, 0,sizeof(x))
- #define pb push_back
- #define mp make_pair
- #define fi first
- #define se second
- #define N 300005
- #define remain(x) if (x > MOD) x -= MOD
- #define ii pair<int, int>
- #define iiii pair< ii , ii >
- #define viiii vector< iiii >
- #define vi vector<int>
- #define vii vector< ii >
- #define bit(x, i) (((x) >> (i)) & 1)
- #define Task "test"
- #define int long long
- using namespace std;
- typedef long double ld;
- const int inf = 1e10;
- const int minf = -1e10;
- int n;
- vector<int> a[N];
- vector<int> s;
- int q, node;
- int nn;
- int color[N], vst[N];
- void readfile()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(0);cout.tie(0);
- if (fopen(Task".inp","r"))
- {
- freopen(Task".inp","r",stdin);
- //freopen(Task".out","w",stdout);
- }
- cin >> n >> q >> node;
- for(int i=1; i<n; i++){
- int u, v;
- cin >> u >> v;
- a[u].pb(v);
- a[v].pb(u);
- }
- for(int i=1; i<=n; i++){
- cin >> color[i];
- }
- }
- int dfs(int u){
- s.pb(u);
- vst[u]=1;
- if (a[u].size()==0)
- return u;
- for(auto v : a[u]){
- if (vst[v]) continue;
- int temp = dfs(v);
- s.pb(temp);
- }
- return u;
- }
- int in[N], ou[N];
- bool fir[N];
- ii b[N*4];
- map<int,int> last;
- struct query {
- int u, v, id;
- bool operator < (const query &q) const {
- return u < q.u;
- }
- } qry[N];
- int bit[N*4];
- int ans[N];
- void increase(int v) {
- for(; v <= nn; v += v & -v) ++bit[v];
- }
- int sum(int v) {
- int res = 0;
- for(; v != 0; v -= v & -v) res += bit[v];
- return res;
- }
- void proc()
- {
- s.pb(dfs(node));
- for(int i=0; i<s.size(); i++){
- int x = s[i];
- if (!fir[x]){
- fir[x] = true;
- in[x] = i+1;
- }
- else ou[x] = i+1;
- }
- nn = s.size();
- for(int i=1; i<=nn; i++){
- int x = color[s[i-1]];
- b[i] = make_pair(last[x],i);
- last[x] = i;
- }
- for(int i=1; i<=n; i++){
- qry[i].u = in[i];
- qry[i].v = ou[i];
- qry[i].id = i;
- }
- sort(qry+1,qry+1+n);
- sort(b+1,b+1+nn);
- int p = nn;
- for(int i=n; i>=1; i--){
- query &Q = qry[i];
- while(b[p].first >= Q.u) increase(b[p--].second);
- ans[Q.id] = (Q.v - Q.u + 1) - (sum(Q.v) - sum(Q.u));
- }
- while (q--){
- int S; cin >> S;
- cout << ans[S] << '\n';
- }
- }
- signed main()
- {
- readfile();
- proc();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement