Cau mày (cây màu)
Xem dạng PDFCho một cây gồm ~n~ đỉnh có gốc tại đỉnh ~1~. Đỉnh thứ ~i~ (~1 \leq i \leq n~) được gán màu sắc là ~c_i~.
Với mỗi đỉnh ~i~, xác định số màu sắc phân biệt có trong cây con gốc ~i~.
Input
Dòng đầu chứa số nguyên dương ~n~ (~1 \leq n \leq 2 \times 10^5~).
Dòng thứ hai chứa ~n~ số nguyên dương cách nhau bởi dấu cách biểu diễn mảng ~c~, với ~c_i~ là màu sắc của đỉnh thứ ~i~ (~1 \leq c_i \leq 10^9~).
~n-1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~a, b~ biểu diễn một cạnh hai chiều giữa đỉnh ~a~ và ~b~ (~1 \leq a,b \leq n~).
Output
Gồm một dòng duy nhất chứa ~n~ số nguyên cách nhau bởi dấu cách, số thứ ~i~ là số màu sắc phân biệt trong tất cả các đỉnh thuộc cây con gốc ~i~.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | 40 | ~n \leq 5000~ |
| 2 | 60 | ~n \leq 2 \times 10^5~ |
Sample Input 1
5
2 3 2 2 1
1 2
1 3
3 4
3 5
Sample Output 1
3 1 2 1 1
Sample Input 2
4
1 1 3 1000
1 2
2 3
2 4
Sample Output 2
3 3 1 1
Notes
Trong test đầu tiên, cây con của đỉnh ~1~ bao gồm tất cả các đỉnh trong cây, mang ~3~ giá trị màu sắc khác nhau. Cây con của đỉnh ~3~ bao gồm ba đỉnh là ~3, 4, 5~ lần lượt mang các màu ~2, 2, 1~, có tất cả ~2~ màu sắc phân biệt là màu ~1~ và ~2~.
Trong test thứ hai, cây con của đỉnh ~1~ và đỉnh ~2~ đều có ~3~ màu sắc phân biệt là màu ~1, 3, 1000~.
Bình luận
include<bits/stdc++.h>
define fastio iosbase::syncwith_stdio(0);cin.tie(0);cout.tie(0);
define ll long long
define pb push_back
define pii pair<int,int>
define pll pair<ll,ll>
define fi first
define se second
define getbit(x,k) ((x)&(1<<k))
define MASK(x) (((1)<<(x))-1)
define M 20
const ll inf=1e9; const int maxn=2e5+5,mod=1e18+9; using namespace std;
inline ll bp(ll a){return a*a;} mt1993764 rang(chrono::steadyclock::now().timesinceepoch().count());
int n,A[maxn]; vector<int>eg[maxn]; int old[maxn],ans[maxn]; int tin[maxn],tout[maxn],counter=0; struct SegTree { int sz; vector<int>st; SegTree(){} SegTree(int sz): sz(sz),st(sz4+10,0) {} void update(int l, int r, int lab, int a, int val) { if(l==r) { st[lab]=val; return; } int mid=(l+r)/2; if(a<=mid) update(l,mid,lab2,a,val); else update(mid+1,r,lab2+1,a,val); st[lab]=st[lab2]+st[lab2+1]; } int get(int l, int r, int lab, int a, int b) { if(l>b || r<a) return 0; if(l>=a && r<=b) return st[lab]; int mid=(l+r)/2; return get(l,mid,lab2,a,b)+get(mid+1,r,lab*2+1,a,b); } }f;
void dfs(int u, int p) { tin[u]=++counter; for(int v:eg[u])if(v!=p) dfs(v,u); tout[u]=counter; if(old[A[u]]!=-1) f.update(1,f.sz,1,tin[old[A[u]]],0); f.update(1,f.sz,1,tin[u],1);old[A[u]]=u; ans[u]=f.get(1,f.sz,1,tin[u],tout[u]); } vector<int>N; void nen() { sort(N.begin(),N.end()); N.erase(unique(N.begin(),N.end()),N.end()); for(int i=1;i<=n;i++) A[i]=lower_bound(N.begin(),N.end(),A[i])-N.begin()+1; } int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>A[i]; N.pb(A[i]); } nen(); for(int i=1;i<n;i++) { int a,b;cin>>a>>b; eg[a].pb(b);eg[b].pb(a); } memset(old,-1,sizeof old); f=SegTree(n); dfs(1,1); for(int i=1;i<=n;i++) cout<<ans[i]<<' '; }
sao copy code của tôi vậy bạn =))))
Spoil lời giải :
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.