•参考资料
•题意
给出一棵树，根节点为1。
每条边有一个权值，树上有红色结点 m 个，其花费为 0 ，其余为黑色；
每个黑色结点的花费为其到最近红色祖先的经过的路径权值之和。
有 q 次询问，每次给出一个点集；
问将树上任意一个结点涂成红色结点后，点集中所有点的花费的最大值的最小是多少。
•题解
相关变量解释：
sum : 每次询问中询问的点集个数
a[ ] : 存储每次询问到的点集
costR[i] : 结点 i 距其最近红色祖先的花费
预处理每个点到根的距离cost、到最近红色祖先的距离 costR 和 ST 表。
对于每次询问，将a[ ] 按 costR 从大到小排序，在 0~costR[a[0]] 范围内二分答案；
对所有大于答案的点求它们的公共祖先（利用ST表可以O(1)求两点的公共祖先），将其涂红；
之后计算每个大于答案的点的新花费是否小于答案。
•Code
#include<iostream>
#include<vector>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
#define pb push_back
#define ll long long
#define mem(a,b) (memset(a,b,sizeof a))
const int maxn=1e5+; int n,m,q;
//===============Restore Graph============
struct Node
{
int to;
ll w;
Node(int to,int w):to(to),w(w){}
};
vector<Node >G[maxn];
void addEdge(int u,int v,int w)
{
G[u].pb(Node(v,w));
G[v].pb(Node(u,w));
}
//=========================================
int vs[*maxn];//欧拉序列，范围区间为 [1,total]
int depth[*maxn];//欧拉序列对应的深度序列
int pos[maxn];//pos[i] : 结点 i 再欧拉序列中第一次出现的位置
ll cost[maxn];//cost[i] : 结点 i 距根据点的距离
ll costR[maxn];//costR[i] : 结点 i 距最近红色祖先结点的距离，初始化为 -1
int total;//欧拉序列的大小
void dfs(int u,int f,int dep,ll dis)
{
vs[++total]=u;
depth[total]=dep;
pos[u]=total;
cost[u]=dis;
for(int i=;i < G[u].size();++i)
{
Node e=G[u][i];
if (e.to == f)
continue;
costR[e.to]=(costR[e.to] == ? :costR[u]+e.w);
dfs(e.to,u,dep+,dis+e.w);
vs[++total]=u;
depth[total]=dep;
}
}
//==================RMQ======================
struct Node2
{
int mm[ * maxn];
int dp[ * maxn][];
void ST()
{
int n=total;
mm[] = -;
for (int i = ; i <= n; i++)
{
mm[i]=((i&(i-))==) ? mm[i - ] + :mm[i - ];
dp[i][]=i;
}
for (int j=;j <= mm[n];j++)
for (int i=;i+(<<j)- <= n;i++)
if(depth[dp[i][j - ]] < depth[dp[i+(<<(j-))][j-]])
dp[i][j]=dp[i][j-];
else
dp[i][j]=dp[i+(<<(j-))][j-];
}
int Lca(int u, int v)
{
u=pos[u],v=pos[v];
if (u > v)
swap(u, v);
int k = mm[v-u+];
if(depth[dp[u][k]] <= depth[dp[v-(<<k)+][k]])
return vs[dp[u][k]];
return vs[dp[v-(<<k)+][k]];
}
}_rmq;
//==========================================
int a[maxn];
int sum;
bool cmp(int a, int b)
{
return costR[a] > costR[b];
}
bool Check(ll x)
{
if(costR[a[]] <= x)
return true;
int lca=a[];
for(int i=;i < sum;i++)
{
if(costR[a[i]] <= x)
break;
lca=_rmq.Lca(lca,a[i]);
}
for(int i = ;i < sum;i++)
{
if(costR[a[i]] <= x)
return true;
if(cost[a[i]]-cost[lca] > x)
return false;
}
return true;
}
void Solve()
{
dfs(,-,,);
_rmq.ST();
while(q--)
{
scanf("%d",&sum);
for (int i=;i < sum; i++)
scanf("%d",&a[i]);
sort(a,a+sum,cmp);
ll l=,r=costR[a[]];
while(l < r)
{
ll mid=(l+r)/;
if(Check(mid))
r=mid;
else
l=mid + ;
}
printf("%lld\n",l);
}
}
void init()
{
mem(costR,-);
total=;
for(int i=;i < maxn;++i)
G[i].clear();
}
int main()
{
int t;
scanf("%d", &t);
while(t--)
{
init();
scanf("%d%d%d",&n,&m,&q);
while(m--)
{
int red;
scanf("%d",&red);
costR[red]=;
}
costR[]=;
for(int i=;i<n;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
addEdge(u,v,w);
}
Solve();
}
return ;
}
•出现的问题
1、用 vector 存储图比用 链式前向星存储图要慢
(1)vector :
(2)链式前向星：
2、平常一直在用的RMQ会超时
//=====================RMQ===================
struct Node1
{
int dp[][*maxn];
void Preset()
{
for(int i=;i < *maxn;++i)
dp[][i]=i;
}
void ST()
{
int k=log(total)/log();
for(int i=;i <= k;++i)
for(int j=;j <= (total-(<<i)+);++j)
if(depth[dp[i-][j]] > depth[dp[i-][j+(<<(i-))]])
dp[i][j]=dp[i-][j+(<<(i-))];
else
dp[i][j]=dp[i-][j];
}
int Lca(int u,int v)
{
u=pos[u],v=pos[v];
if(u > v)
swap(u,v);
int k=log(v-u+)/log();
if(depth[dp[k][u]] > depth[dp[k][v-(<<k)+]])
return vs[dp[k][v-(<<k)+]];
return vs[dp[k][u]];
}
}_rmq;
//===========================================TLE
//==================RMQ======================
struct Node2
{
int mm[ * maxn];
int dp[ * maxn][];
void ST()
{
int n=total;
mm[] = -;
for (int i = ; i <= n; i++)
{
mm[i]=((i&(i-))==) ? mm[i - ] + :mm[i - ];
dp[i][]=i;
}
for (int j=;j <= mm[n];j++)
for (int i=;i+(<<j)- <= n;i++)
if(depth[dp[i][j - ]] < depth[dp[i+(<<(j-))][j-]])
dp[i][j]=dp[i][j-];
else
dp[i][j]=dp[i+(<<(j-))][j-];
}
int Lca(int u, int v)
{
u=pos[u],v=pos[v];
if (u > v)
swap(u, v);
int k = mm[v-u+];
if(depth[dp[u][k]] <= depth[dp[v-(<<k)+][k]])
return vs[dp[u][k]];
return vs[dp[v-(<<k)+][k]];
}
}_rmq;
//==========================================AC
3、cost[ ] 很有用，如果 Check( ) 中不加
if(cost[a[i]]-cost[lca] > x)
return false;会返回 WA，具体为什么，明天再好好想想%%%%%%%%%
分割线：2019.5.8
中石油的这场重现赛又让我回想起了这道题留下的疑惑；
现在再想想这道题，思路清晰了些许；
一些不理解的地方瞬间顿悟了；
ST表处理RMQ中，会多次求解 log2(x)，这种算式是比较耗时的，我们预处理出所需的log2(x)；
logTwo[i]=log2(i);如何预处理呢？
首先想一下，三位数的二进制数的最大值为 111(2)，四位数的二进制数的最小值为 1000(2)；
两者的关系是 (111)&(1000) = 0 , 而对于任意三位二进制数 x,y ，(x&y) != 0；
有了这个关系后，就可以这么预处理了：
logTwo[]=-;
for(int i=;i <= n;++i)
logTwo[i]=(i&(i-)) == ? logTwo[i-]+:logTwo[i-];这就是之前一直不理解的ST表加速的地方；
•Code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define INFll 0x3f3f3f3f3f3f3f3f
const int maxn=1e5+; int n,m,q;
ll C[maxn];///C[i]:节点i到根节点1的花费
ll CR[maxn];///CR[i]:节点i到其最近的红色祖先节点的花费
int num;
int head[maxn];
struct Edge
{
int to;
ll w;
int next;
}G[maxn<<];
void addEdge(int u,int v,ll w)
{
G[num]={v,w,head[u]};
head[u]=num++;
}
struct LCA
{
int vs[maxn<<];///欧拉序列
int dep[maxn<<];///欧拉序列中的节点对应的深度序列
int pos[maxn<<];///pos[i]:节点i在欧拉序列中第一次出现的位置
int cnt;
int logTwo[maxn<<];///logTwo[i]:log2(i)
int dp[maxn<<][];///dp[i][j]:[i,i+2^j-1]深度最小的点的下标（欧拉序列中的下标）
void DFS(int u,int f,int depth,ll dist)
{
vs[++cnt]=u;
dep[cnt]=depth;
pos[u]=cnt;
C[u]=dist;
for(int i=head[u];~i;i=G[i].next)
{
int v=G[i].to;
ll w=G[i].w;
if(v == f)
continue;
CR[v]=min(CR[v],CR[u]+w);
DFS(v,u,depth+,dist+w);
vs[++cnt]=u;
dep[cnt]=depth;
}
}
void ST()
{
logTwo[]=-;
for(int i=;i <= cnt;++i)
{
dp[i][]=i;
///:后的语句写错了，刚开始写成了logTwo[i]，debug了好一会
logTwo[i]=(i&(i-)) == ? logTwo[i-]+:logTwo[i-];
}
for(int k=;k <= logTwo[cnt];++k)
for(int i=;i+(<<k)- <= cnt;++i)
if(dep[dp[i][k-]] > dep[dp[i+(<<(k-))][k-]])
dp[i][k]=dp[i+(<<(k-))][k-];
else
dp[i][k]=dp[i][k-];
}
void lcaInit(int root)
{
cnt=;
DFS(root,root,,);
ST();
}
int lca(int u,int v)///返回节点u,v的LCA
{
u=pos[u];
v=pos[v]; if(u > v)
swap(u,v); int k=logTwo[v-u+];
if(dep[dp[u][k]] > dep[dp[v-(<<k)+][k]])
return vs[dp[v-(<<k)+][k]];
else
return vs[dp[u][k]];
}
}_lca; int qCnt;
int query[maxn<<]; bool Check(ll mid)
{
int lca=;///不满足条件的点的LCA
for(int i=;i <= qCnt;++i)
{
if(CR[query[i]] <= mid)
continue;
if(lca == )
lca=query[i];
else/// > mid的点LCA
lca=_lca.lca(lca,query[i]);
} for(int i=;i <= qCnt;++i)
{
if(CR[query[i]] <= mid)
continue; ///如果将lca点涂红后还不能使其 <= mid，返回false
if(C[query[i]]-C[lca] > mid)
return false;
}
return true;
}
void Solve()
{
_lca.lcaInit(); for(int i=;i <= q;++i)
{
scanf("%d",&qCnt); ll l=-,r=;
for(int j=;j <= qCnt;++j)
{
scanf("%d",query+j);
r=max(r,CR[query[j]]);
} while(r-l > )
{
ll mid=l+((r-l)>>);
if(Check(mid))
r=mid;
else
l=mid;
}
printf("%lld\n",r);
}
}
void Init()
{
num=;
mem(head,-);
mem(CR,INFll);///初始化为最大值
}
int main()
{
// freopen("C:\\Users\\hyacinthLJP\\Desktop\\in&&out\\contest","r",stdin);
int test;
scanf("%d",&test);
while(test--)
{
Init();
scanf("%d%d%d",&n,&m,&q);
for(int i=;i <= m;++i)
{
int red;
scanf("%d",&red);
CR[red]=;
}
CR[]=;
for(int i=;i < n;++i)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
addEdge(u,v,w);
addEdge(v,u,w);
}
Solve();
}
return ;
}