QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#185005 | #7103. Red Black Tree | EastKing | WA | 1193ms | 42968kb | C++17 | 4.0kb | 2023-09-21 15:41:20 | 2023-09-21 15:41:20 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int M=1e5+5;
typedef long long ll;
int n;
bool red[M];
vector<pair<int,ll>>G[M],E[M];
int tot,dfn[M],fa[20][M],dep[M];
int bel[M];
ll val[M];
int lca(int x,int y){
if(dep[x]>dep[y])swap(x,y);
int tmp=dep[y]-dep[x];
for(int i=0;tmp;i++){
if(tmp&1)y=fa[i][y];
tmp>>=1;
}
if(x==y)return x;
for(int i=19;i>=0;i--){
if(fa[i][x]==fa[i][y])continue;
x=fa[i][x];
y=fa[i][y];
}
return fa[0][x];
}
void init(){//dfn+倍增
tot=0;
function<void(int,int)>dfs=[&](int x,int f){
if(red[x])bel[x]=x;
dfn[x]=++tot;
dep[x]=dep[f]+1;
fa[0][x]=f;
for(int i=1;i<20;i++)fa[i][x]=fa[i-1][fa[i-1][x]];
for(auto [y,w]:G[x]){
if(y==f)continue;
val[y]=val[x]+w;
bel[y]=bel[x];
dfs(y,x);
}
};
bel[1]=1;
val[1]=0;
dfs(1,0);
}
ll get_val(int a,int b){
if(dep[a]<dep[b])swap(a,b);
return val[a]-val[b];
}
bool mark[M];//记录
int build(vector<int>&Q){
//排序+去重
sort(Q.begin(),Q.end(),[&](int a,int b){return dfn[a]<dfn[b];});
Q.erase(unique(Q.begin(),Q.end()),Q.end());
//求虚树点+连边
int len=Q.size();
vector<int>stk(len*2+1);
int top=0;
stk[++top]=Q[0];
for(int i=1;i<len;i++){
int now=Q[i];
int lc=lca(now,stk[top]);
while(dep[lc]<dep[stk[top-1]]){
E[stk[top-1]].push_back({stk[top],get_val(stk[top-1],stk[top])});
top--;
}
if(dep[lc]>dep[stk[top-1]]){
if(lc==stk[top]){
stk[++top]=now;
}else{
E[lc].push_back({stk[top],get_val(lc,stk[top])});
stk[top]=lc;
stk[++top]=now;
}
}else if(lc==stk[top-1]){
E[stk[top-1]].push_back({stk[top],get_val(stk[top-1],stk[top])});
stk[top]=now;
}
}
while(top>1){
E[stk[top-1]].push_back({stk[top],get_val(stk[top-1],stk[top])});
top--;
}
return stk[top];//返回树根
}
ll mxe[M],mxv[M];
int Lt[M],Rt[M],tid[M],tcnt;
ll mxL[M],mxR[M];
void dfs(int x){//树形dp
mxe[x]=-1e18;
mxv[x]=0;
Lt[x]=++tcnt;
tid[tcnt]=x;
for(auto [y,w]:E[x]){
dfs(y);
mxv[x]=max(mxv[x],mxv[y]);
if(!red[y]){
mxe[x]=max(mxe[x],mxe[y]+w);
}
}
if(mark[x]){
mxe[x]=max(mxe[x],0ll);
}
if(red[x]){
mxv[x]=max(mxv[x],mxe[x]);
}
Rt[x]=tcnt;
}
ll Ans;
void clear(int x){//清空虚树边
mark[x]=0;
//printf("x=%d mxe=%lld other=%lld\n",x,mxe[x],max(mxL[Lt[x]-1],mxR[Rt[x]+1]));
Ans=min(Ans,max(max(mxe[x],mxv[x]),max(mxL[Lt[x]-1],mxR[Rt[x]+1])));
for(auto [y,w]:E[x]){
clear(y);
}
E[x].clear();
}
int main(){
int cas;
scanf("%d",&cas);
while(cas--){
int m,q;
scanf("%d %d %d",&n,&m,&q);
//clear
for(int i=1;i<=n;i++){
red[i]=0;
G[i].clear();
}
//
for(int i=1;i<=m;i++){
int x;
scanf("%d",&x);
red[x]=1;
}
for(int i=1;i<n;i++){
int a,b;
ll c;
scanf("%d %d %lld",&a,&b,&c);
G[a].push_back({b,c});
G[b].push_back({a,c});
}
init();//dfs+倍增
while(q--){
int k;
scanf("%d",&k);
//读入关键点
vector<int>Q;
for(int i=0;i<k;i++){
int x;
scanf("%d",&x);
Q.push_back(x);
mark[x]=1;//记录关键点信息
}
//建虚树+树形dp
int rt=build(Q);
tcnt=0;
dfs(rt);
mxL[0]=0,mxR[tcnt+1]=0;
for(int i=1;i<=tcnt;i++){
mxL[i]=mxL[i-1];
int x=tid[i];
if(mark[x]){
mxL[i]=max(mxL[i],val[x]-val[bel[x]]);
}
}
for(int i=tcnt;i>=1;i--){
mxR[i]=mxR[i+1];
int x=tid[i];
if(mark[x]){
mxR[i]=max(mxR[i],val[x]-val[bel[x]]);
}
}
Ans=mxR[1];
clear(rt);//记得清空
//printf("ans:");
printf("%lld\n",Ans);
}
}
return 0;
}
/*
2
12 2 4
1 9
1 2 1
2 3 4
3 4 3
3 5 2
2 6 2
6 7 1
6 8 2
2 9 5
9 10 2
9 11 3
1 12 10
3 3 7 8
4 4 5 7 8
4 7 8 10 11
3 4 5 12
3 2 3
1 2
1 2 1
1 3 1
1 1
2 1 2
3 1 2 3
*/
/*
1
12 2 4
1 9
1 2 100000000000
2 3 400000000000
3 4 300000000000
3 5 200000000000
2 6 200000000000
6 7 100000000000
6 8 200000000000
2 9 500000000000
9 10 200000000000
9 11 300000000000
1 12 1000000000000
3 3 7 8
4 4 5 7 8
4 7 8 10 11
3 4 5 12
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 18892kb
input:
2 12 2 4 1 9 1 2 1 2 3 4 3 4 3 3 5 2 2 6 2 6 7 1 6 8 2 2 9 5 9 10 2 9 11 3 1 12 10 3 3 7 8 4 4 5 7 8 4 7 8 10 11 3 4 5 12 3 2 3 1 2 1 2 1 1 3 1 1 1 2 1 2 3 1 2 3
output:
4 5 3 8 0 0 0
result:
ok 7 lines
Test #2:
score: -100
Wrong Answer
time: 1193ms
memory: 42968kb
input:
522 26 1 3 1 1 4 276455 18 6 49344056 18 25 58172365 19 9 12014251 2 1 15079181 17 1 50011746 8 9 2413085 23 24 23767115 22 2 26151339 26 21 50183935 17 14 16892041 9 26 53389093 1 20 62299200 24 18 56114328 11 2 50160143 6 26 14430542 16 7 32574577 3 16 59227555 3 15 8795685 4 12 5801074 5 20 57457...
output:
148616264 148616264 0 319801028 319801028 255904892 317070839 1265145897 1265145897 1072765445 667742619 455103436 285643094 285643094 285643094 317919339 0 785245841 691421476 605409472 479058444 371688030 303203698 493383271 919185207 910180170 919185207 121535083 181713164 181713164 181713164 181...
result:
wrong answer 427th lines differ - expected: '1455744935', found: '1637098612'