//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize(3)
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC target("sse3","sse2","sse")
//#pragma GCC target("avx","sse4","sse4.1","sse4.2","ssse3")
//#pragma GCC target("f16c")
//#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
//#pragma GCC diagnostic error "-fwhole-program"
//#pragma GCC diagnostic error "-fcse-skip-blocks"
//#pragma GCC diagnostic error "-funsafe-loop-optimizations"
//#pragma GCC diagnostic error "-std=c++14"
#include "bits/stdc++.h"
//#include "ext/pb_ds/tree_policy.hpp"
//#include "ext/pb_ds/assoc_container.hpp"
#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define fr(x) freopen(x,"r",stdin)
#define fw(x) freopen(x,"w",stdout)
#define iout(x) printf("%d\n",x)
#define lout(x) printf("%lld\n",x)
#define REP(x,l,u) for(ll x = l;x<u;x++)
#define RREP(x,l,u) for(ll x = l;x>=u;x--)
#define complete_unique(a) a.erase(unique(a.begin(),a.end()),a.end())
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) a.begin(),a.end()
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define MP make_pair
#define sqr(x) ((x)*(x))
#define lowbit(x) ((x)&(-(x)))
#define lson (ind<<1)
#define rson (ind<<1|1)
#define se second
#define fi first
#define sz(x) ((int)x.size())
#define EX0 exit(0);
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
using namespace std;
typedef vector<ll> VLL;
typedef vector<int> VI;
const int block_size = 320;
typedef complex<ll> point;
const ll mod = 1e9+7;
const ll inf = 1e9+7;
const ld eps = 1e-9;
const db PI = atan(1)*4;
template<typename T>
inline int sign(const T&a) {
if(a<0)return -1;
if(a>0)return 1;
return 0;
}
string to_string(string s) {
return '"' + s + '"';
}
string to_string(const char* s) {
return to_string((string) s);
}
string to_string(bool b) {
return (b ? "true" : "false");
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A>
string to_string(A v) {
bool first = true;
string res = "{";
for (const auto &x : v) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(x);
}
res += "}";
return res;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << to_string(H);
debug_out(T...);
}
#ifndef ONLINE_JUDGE
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define dbg(...) {}
#endif
template<typename T,typename S>inline bool upmin(T&a,const S&b){return a>b?a=b,1:0;}
template<typename T,typename S>inline bool upmax(T&a,const S&b){return a<b?a=b,1:0;}
template<typename T> inline void in(T &x) {
x = 0;
T f = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') f = -1;
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + ch - '0';
ch = getchar();
}
x *= f;
}
ll twop(int x) {
return 1LL<<x;
}
template<typename A,typename B > inline void in(A&x,B&y) {
in(x);
in(y);
}
template<typename A,typename B,typename C>inline void in(A&x,B&y,C&z) {
in(x);
in(y);
in(z);
}
template<typename A,typename B,typename C,typename D> inline void in(A&x,B&y,C&z,D&d) {
in(x);
in(y);
in(z);
in(d);
}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
namespace SOLVE {
int color[100010];
int relabel[100010];
struct SegTree{
static const int maxn = 100010;
struct node{
int l,r;
int cover;
};
node no[maxn*4];
void push_up(int ind){
}
void push_down(int ind){
if(no[ind].cover >= 1){
no[lson].cover = no[rson].cover = no[ind].cover;
no[ind].cover = 0;
}
}
void build(int l,int r,int ind){
no[ind].l = l;
no[ind].r = r;
if(l == r){
(no[ind].cover = relabel[l]);
}else{
int mid = (l+r)/2;
build(l,mid,lson);
build(mid+1,r,rson);
push_up(ind);
}
}
void update(int l,int r,int ind,int val){
if(l>no[ind].r || r<no[ind].l)return;
if(l<=no[ind].l && no[ind].r <= r){
no[ind].cover = val;
}else{
push_down(ind);
update(l,r,lson,val);
update(l,r,rson,val);
push_up(ind);
}
}
void query(int l,int r,int ind,vector<PII>& ans){
if(l>no[ind].r || r<no[ind].l)return;
if(no[ind].cover){
ans.PB(MP(min(r,no[ind].r) - max(l,no[ind].l)+1,no[ind].cover));
}else{
push_down(ind);
query(l,r,lson,ans);
query(l,r,rson,ans);
push_up(ind);
}
}
};
SegTree tree;
namespace HLD {
//0不能被使用
struct edge {
int to;
edge(int x):to(x){}
};
const int root = 1;
const int maxn = 100010;
vector<edge>adj[maxn];
int dfnToID[maxn],dfn[maxn],head[maxn],fa[maxn],dep[maxn],size[maxn],heavy[maxn],r[maxn],cnt = 1;
void firstDfs(int cur,int _fa) {
dep[cur] = dep[_fa]+1;
size[cur]=1;
fa[cur] = _fa;
for(auto e:adj[cur]) {
if(e.to!=_fa) {
firstDfs(e.to,cur);
size[cur]+=size[e.to];
}
}
int heavyChild = 0;
for(auto e:adj[cur]) {
if(e.to!=_fa) {
if(size[e.to]>size[heavyChild]) {
heavyChild = e.to;
}
}
}
heavy[cur] = heavyChild;
}
void secondDfs(int cur,int _fa) {
if(cur!=heavy[_fa]) {
head[cur] = cur;
} else {
head[cur] = head[_fa];
}
dfn[cur] = cnt++;
r[cur] = dfn[cur];
dfnToID[dfn[cur]] = cur;
if(!heavy[cur])return;
secondDfs(heavy[cur],cur);
r[cur] = r[heavy[cur]];
for(auto e:adj[cur]) {
if(e.to==_fa||e.to==heavy[cur])continue;
secondDfs(e.to,cur);
r[cur] = r[e.to];
}
}
void init() {
firstDfs(root,0);
secondDfs(root,0);
}
int kthFather(int k,int cur) {
while(k) {
if(head[cur] == cur) {
k--;
cur = fa[head[cur]];
} else {
if(dep[cur]-dep[head[cur]]<=k) {
k-=dep[cur]-dep[head[cur]];
cur = head[cur];
} else {
return dfnToID[dfn[cur]-k];
}
}
}
return cur;
}
int LCA(int u,int v) {
while(head[u]!=head[v]) {
if(dep[head[u]]>dep[head[v]])swap(u,v);
v = fa[head[v]];
}
if(dep[u]<dep[v])return u;
return v;
}
int dis(int u,int v){
return dep[u]+dep[v]-2*dep[LCA(u, v)];
}
void getColors(int u,vector<PII>&ans){
if(u == 0)return;
getColors(fa[head[u]], ans);
tree.query(dfn[head[u]], dfn[u], 1, ans);
}
ll gao(vector<PII>::iterator s,vector<PII>::iterator t){
if(t == s+1)return 0;
auto mid = s + (t-s)/2;
ll ans = gao(s, mid) + gao(mid, t);
ll cnt = 0;
auto cur = s;
for(auto i = mid;i!=t;i++){
while(cur!=mid and cur->se > i->se){
cnt += cur->fi;
++cur;
}
ans += cnt * i->fi;
}
inplace_merge(s, mid, t,greater<PII>());
return ans;
}
void solve(int u){
vector<PII>ans;
getColors(u, ans);
int last_color = ans.back().se;
ans.pop_back();
cout<<gao(begin(ans), end(ans))<<endl;
while(u!=0){
tree.update(dfn[head[u]], dfn[u],1,last_color);
u = fa[head[u]];
}
}
}
vector<PII>pr;
void main(){
int n;in(n);
REP(i,1,n+1)in(color[i]);
REP(i,1,n){
int a,b;in(a,b);
HLD::adj[a].PB(b);
pr.PB(MP(a,b));
}
HLD::init();
REP(i,1,n+1){
relabel[HLD::dfn[i]] = color[i];
}
tree.build(1, n, 1);
for(auto i:pr){
HLD::solve(i.se);
}
}
}
signed main() {
int t;
// in(t);
t = 1;
while(t--){
SOLVE::main();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2680 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2808 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
2680 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2680 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2808 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
2680 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2680 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2808 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
2680 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
