一些题目的代码被网站吞了……
Problem B. Red Black Tree
http://acm.zju.edu.cn/onlinejudge/searchProblem.do?contestId=1&titlefrom=0&authorfrom=0&sourcefrom=0&query=The+2018+ACM-ICPC+Asia+Qingdao+Regional+Contest%2C+Online
http://acm.zju.edu.cn/pcpst/index.html
http://acm.zju.edu.cn/contest-materials/qdol2018/qdol2018_problems.pdf
注意是找祖先(红色孩子节点无效)！
先按照花费对节点从大到小进行排序，依次增加一个点，这个点的花费采用从该点到所有新加入点的最近公共祖先的距离，直到遇到花费不可减少，则停止。
注意maxlen！
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+;
const double minv=1e-;
const ll inf=1e18; vector<pair<int,ll> >e[maxn];
int r[maxn],dep[maxn<<],p[maxn<<],lef[maxn],er[],point[maxn],ind,f[maxn<<][];
ll cost[maxn],len[maxn];
bool vis[maxn]; void dfs(int d,ll c,ll l,int deep)
{
vis[d]=;
if (r[d]==)
c=;
cost[d]=c;
len[d]=l;
dep[++ind]=deep;
p[ind]=d;
lef[d]=ind;
vector<pair<int,ll> >::iterator j;
for (j=e[d].begin();j!=e[d].end();j++)
if (!vis[j->first])
{
dfs(j->first,c+j->second,l+j->second,deep+);
dep[++ind]=deep;
p[ind]=d;
}
} int cmp(int a,int b)
{
return cost[a]>cost[b];
} int main()
{
int t,n,m,q,u,v,d,deep,i,j,k;
ll w,result,maxlen;
for (i=;i<=;i++)
er[i]=<<i;
scanf("%d",&t);
while (t--)
{
scanf("%d%d%d",&n,&m,&q);
for (i=;i<=n;i++)
{
r[i]=;
vis[i]=;
e[i].clear();
}
for (i=;i<=m;i++)
scanf("%d",&d),r[d]=;
for (i=;i<n;i++)
{
scanf("%d%d%lld",&u,&v,&w);
e[u].push_back({v,w});
e[v].push_back({u,w});
}
ind=;
dfs(,,,);
for (j=;j<=ind;j++)
f[j][]=j;
deep=(int)(log(ind)/log()+minv);
for (i=;i<=deep;i++)
for (j=,k=er[i-]+;j<=ind-er[i]+;j++,k++)
f[j][i]=(dep[f[j][i-]]<dep[f[k][i-]])?f[j][i-]:f[k][i-];
while (q--)
{
scanf("%d",&m);
for (i=;i<=m;i++)
scanf("%d",&point[i]);
sort(point+,point+m+,cmp);
if (m==)
result=;
else
{
result=cost[point[]];
d=point[];
}
maxlen=len[point[]];
for (i=;i<=m;i++)
{
u=lef[d];
v=lef[point[i]];
if (u>v)
swap(u,v);
deep=(int)(log(v-u+)/log()+minv);
d=(dep[f[u][deep]]<dep[f[v-er[deep]+][deep]])?f[u][deep]:f[v-er[deep]+][deep];
d=p[d];
maxlen=max(maxlen,len[point[i]]);
w=maxlen-len[d];
if (i==m || w>=cost[point[i+]])
{
result=min(result,w);
break;
}
result=min(result,cost[point[i+]]);
}
printf("%lld\n",result);
}
}
return ;
}
/*
10
10 2 100
7 10
1 2 3
1 3 4
1 4 1
2 5 1
3 6 2
5 7 3
3 8 2
4 9 3
9 10 10
5 1 2 3 4 5 */
另外：
对花费采用二分
参见 https://blog.****.net/qq_40993793/article/details/82762766，
每次询问O( klog(w*n) )，(其中排序那块我没看懂，这里的时间复杂度没有算排序)
sum(k)<=2e6,n<=1e5,w<=1e9,
因此log(w*n)=47,maxtime=9.4*10^7，存在超时的可能性(虽然假设的有点。。。)。不太推荐。。。
在zoj测试时，超时了
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+;
const double minv=1e-;
const ll inf=1e18; vector<pair<int,ll> >e[maxn];
int red[maxn],dep[maxn<<],p[maxn<<],lef[maxn],er[],point[maxn],ind,f[maxn<<][];
ll cost[maxn],len[maxn];
bool vis[maxn]; void dfs(int d,ll c,ll l,int deep)
{
vis[d]=;
if (red[d]==)
c=;
cost[d]=c;
len[d]=l;
dep[++ind]=deep;
p[ind]=d;
lef[d]=ind;
vector<pair<int,ll> >::iterator j;
for (j=e[d].begin();j!=e[d].end();j++)
if (!vis[j->first])
{
dfs(j->first,c+j->second,l+j->second,deep+);
dep[++ind]=deep;
p[ind]=d;
}
} int cmp(int a,int b)
{
return cost[a]>cost[b];
} int main()
{
int t,n,m,q,u,v,g,d,deep,i,j,k,l;
ll w,result,r;
bool use;
for (i=;i<=;i++)
er[i]=<<i;
scanf("%d",&t);
while (t--)
{
scanf("%d%d%d",&n,&m,&q);
for (i=;i<=n;i++)
{
red[i]=;
vis[i]=;
e[i].clear();
}
for (i=;i<=m;i++)
scanf("%d",&d),red[d]=;
for (i=;i<n;i++)
{
scanf("%d%d%lld",&u,&v,&w);
e[u].push_back({v,w});
e[v].push_back({u,w});
}
ind=;
dfs(,,,);
for (j=;j<=ind;j++)
f[j][]=j;
deep=(int)(log(ind)/log()+minv);
for (i=;i<=deep;i++)
for (j=,k=er[i-]+;j<=ind-er[i]+;j++,k++)
f[j][i]=(dep[f[j][i-]]<dep[f[k][i-]])?f[j][i-]:f[k][i-];
while (q--)
{
l=; r=;
scanf("%d",&g);
for (i=;i<=g;i++)
{
scanf("%d",&point[i]);
r=max(r,cost[point[i]]);
}
while (l<=r)
{
m=(l+r)>>;
use=;
for (i=;i<=g;i++)
if (cost[point[i]]>m)
{
if (!use)
{
use=;
d=point[i];
continue;
}
u=lef[d];
v=lef[point[i]];
if (u>v)
swap(u,v);
deep=(int)(log(v-u+)/log()+minv);
d=(dep[f[u][deep]]<dep[f[v-er[deep]+][deep]])?f[u][deep]:f[v-er[deep]+][deep];
d=p[d];
if (len[point[]]-len[d]>m)
break;
}
if (i==g+)
r=m-;
else
l=m+;
}
printf("%lld\n",l);
}
}
return ;
}
/*
10
10 2 100
7 10
1 2 3
1 3 4
1 4 1
2 5 1
3 6 2
5 7 3
3 8 2
4 9 3
9 10 10
5 1 2 3 4 5 */