QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#179376 | #5418. Color the Tree | 0x4F5DA2 | TL | 0ms | 11884kb | C++14 | 4.4kb | 2023-09-14 21:01:00 | 2023-09-14 21:01:00 |
Judging History
answer
#include <cstdio>
#include <algorithm>
const int maxn = 100000;
const long long LLF = 10000000000000000;
const int maxlog = 17;
struct node1{
int nxt;
int to;
}edge[maxn * 2 + 10];
int head[maxn + 10];
int top;
void add_e(int u, int v){
++top;
edge[top].nxt = head[u];
edge[top].to = v;
head[u] = top;
return ;
}
int n;
int st[maxlog + 1][maxn + 10];
int log_2[maxn + 10];
int get_mina(int l, int r){
int len = r - l + 1;
int lg = log_2[len];
return std::min(st[lg][l], st[lg][r - (1 << lg) + 1]);
}
int dep[maxn + 10];
int max_dep;
int dfn[maxn + 10];
int top_dfn;
int fa[maxn + 10][maxlog + 1];
//存每个深度的点
node1 edge2[maxn + 10];
int head2[maxn + 10];
int top2;
void add_e2(int u, int v){
++top2;
edge2[top2].nxt = head2[u];
edge2[top2].to = v;
head2[u] = top2;
}
//存虚树
node1 edge3[maxn + 10];
int head3[maxn + 10];
int top3;
void add_e3(int u, int v){
++top3;
edge3[top3].nxt = head3[u];
edge3[top3].to = v;
head3[u] = top3;
}
void dfs1(int x){
dep[x] = dep[fa[x][0]] + 1;
if(max_dep < dep[x])
max_dep = dep[x];
add_e2(dep[x], x);
dfn[x] = ++top_dfn;
for(int i = head[x]; i; i = edge[i].nxt){
int y = edge[i].to;
if(y != fa[x][0]){
fa[y][0] = x;
dfs1(y);
}
}
}
int LCA(int x, int y){
if(dep[x] < dep[y]){
int temp = x;
x = y;
y = temp;
}
for(int i = maxlog; i >= 0; --i){
if(dep[x] - (1 << i) >= dep[y]){
x = fa[x][i];
}
}
if(x == y)
return x;
for(int i = maxlog; i >= 0; --i){
if(fa[x][i] != fa[y][i]){
x = fa[x][i];
y = fa[y][i];
}
}
return fa[x][0];
}
int key_node[maxn + 10];
int top_key;
bool cmp(int a, int b){
return dfn[a] < dfn[b];
}
int sta[maxn + 10];
int tops;
long long ans[maxn + 10];
long long dp[maxn + 10];
int now_d;
void dfs2(int x, int fa){
if(dep[x] == now_d){
dp[x] = (long long)get_mina(now_d - dep[fa] - 1, now_d - dep[x]);
return ;
}
long long temp = 0;
for(int i = head3[x]; i; i = edge3[i].nxt){
int y = edge3[i].to;
dfs2(y, x);
temp = temp + dp[y];
}
dp[x] = std::min((long long)get_mina(now_d - dep[fa] - 1, now_d - dep[x]), temp);
return ;
}
int main(){
log_2[1] = 0;
for(int i = 2; i <= maxn; ++i){
log_2[i] = log_2[(i >> 1)] + 1;
}
int T;
scanf("%d", &T);
// if(T == 3000)
// T = 1;
while(T--){
scanf("%d", &n);
for(int i = 0; i < n; ++i){
scanf("%d", &st[0][i]);
}
for(int i = 1; i <= maxlog; ++i){
for(int j = 0; j + (1 << i) - 1 < n; ++j){
st[i][j] = std::min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
}
}
int u, v;
for(int i = 1; i < n; ++i){
scanf("%d%d", &u, &v);
add_e(u, v);
add_e(v, u);
}
fa[1][0] = 0;
dfs1(1);
for(int i = 1; i <= maxlog; ++i){
for(int j = 1; j <= n; ++j){
fa[j][i] = fa[fa[j][i - 1]][i - 1];
}
}
/*while(1){
scanf("%d%d", &u, &v);
printf("%d\n", LCA(u, v));
}*/
long long final_ans = 0;
for(int i = 1; i <= max_dep; ++i){
//建立虚树
top_key = 0;
tops = 0;
for(int j = head2[i]; j; j = edge2[j].nxt){
++top_key;
key_node[top_key] = edge2[j].to;
}
std::sort(key_node + 1, key_node + 1 + top_key, cmp);
++tops;
sta[tops] = 1;
for(int j = 1; j <= top_key; ++j){
if(key_node[j] == 1)
continue ;
int l = LCA(key_node[j], sta[tops]);
if(l == sta[tops]){
++tops;
sta[tops] = key_node[j];
}
else{
while(dfn[sta[tops - 1]] > dfn[l]){
add_e3(sta[tops - 1], sta[tops]);
--tops;
}
if(dfn[sta[tops - 1]] == dfn[l]){
add_e3(sta[tops - 1], sta[tops]);
--tops;
}
else{
add_e3(l, sta[tops]);
sta[tops] = l;
}
++tops;
sta[tops] = key_node[j];
}
}
for(int i = 1; i < tops; ++i){
add_e3(sta[i], sta[i + 1]);
}
//计算
now_d = i;
dfs2(1, 0);
final_ans = final_ans + dp[1];
//清空
top3 = 0;
head3[1] = 0;
for(int j = 1; j <= top_key; ++j){
head3[key_node[j]] = 0;
}
}
printf("%lld\n", final_ans);
//清空
top2 = 0;
for(int i = 1; i <= max_dep; ++i)
head2[i] = 0;
top = 0;
for(int i = 1; i <= n; ++i){
head[i] = 0;
}
max_dep = 0;
top_dfn = 0;
}
return 0;
}
/*
1
5
10 5 1 100 1000
1 2
2 3
2 4
4 5
*/
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 11884kb
input:
3 4 10 15 40 1 1 2 2 3 2 4 5 10 5 1 100 1000 1 2 2 3 2 4 4 5 4 1000 200 10 8 1 2 2 3 3 4
output:
35 17 1218
result:
ok 3 number(s): "35 17 1218"
Test #2:
score: -100
Time Limit Exceeded
input:
3000 54 43 44 11 49 17 14 7 30 35 12 34 14 15 8 29 47 30 31 39 17 26 23 26 45 34 50 49 13 35 18 29 15 13 44 47 5 22 20 19 46 30 22 26 13 47 46 43 27 48 48 13 14 30 44 1 2 1 3 2 4 3 5 4 6 2 7 4 8 1 9 3 10 1 11 8 12 2 13 9 14 1 15 1 16 15 17 15 18 7 19 1 20 19 21 13 22 10 23 17 24 9 25 9 26 24 27 8 28...