可信赖的丹阳网站建设,山东济南网站建设公司排名,做网站美工的前途怎么样,网站制造Red Black Tree 磨磨蹭蹭地写虚树#xff0c;结果半天没出来。大佬说 二分 求公共节点的lca#xff0c;一下就出来了 二分就是取那些要变更的点的lca 然后判断这样log^2#xff0c;好像也可以排序差分区间和弄到log#xff0c;虚树就是暴力枚举然后换根dp#xff0c;没…Red Black Tree 磨磨蹭蹭地写虚树结果半天没出来。大佬说 二分 求公共节点的lca一下就出来了 二分就是取那些要变更的点的lca 然后判断这样log^2好像也可以排序差分区间和弄到log虚树就是暴力枚举然后换根dp没弄好debug一下午。 虚树
// 基本没啥用就 两个函数是要想的其他都是虚树构造必须虚树构造相关操作
void dfs(int u, int f);
int lca(int u, int v);
LL build(int n);需要思考的操作
LL dfs(int u); // 处理 ma ,K 和 L;
LL df(int u, LL k); int h[N], ne[N1], e[N1], w[N1], idx;
void add(int a, int b, int c){e[idx]b,ne[idx]h[a],w[idx]c,h[a]idx;return ;}int dfn[N], cv, fa[N][20], deep[N];
LL mi[N], ma[N], K[N], L[N], de[N];
// mi[i] i点的值 ma[i] i为根的子树的值的最大值
// K[i] 以i为根的子树 到i的路径上有红色点的值的最大值L[i] 以i为根的子树 到 i的路径上没有红色点的值的最大值
// de[i] i 到 整棵树的根节点的路径和 用来判断 两点之间是否有红色点
bool c[N]; // 1 代表是红色点 void dfs(int u, int f) // 预处理 mi lca
{dfn[u] cv ; deep[u] deep[f] 1;for(int i 1;i 20;i ) fa[u][i] fa[fa[u][i-1]][i-1];for(int i h[u];~i ;i ne[i]){if(e[i] f)continue;fa[e[i]][0] u; mi[e[i]] c[e[i]] ? 0 : mi[u] w[i]; de[e[i]] de[u] w[i];dfs(e[i], u);}
}int lca(int u, int v)
{if(deep[u]deep[v])swap(u, v);int x deep[u] - deep[v];for(int i 0;i 20;i )if(xi1)u fa[u][i];if(u v)return v;for(int i 19;i 0;i --)if(fa[u][i] ! fa[v][i])u fa[u][i], v fa[v][i];return fa[u][0];
}
int a[N];
bool dis[N];
bool cmp(int a,int b){return dfn[a]dfn[b];}bool in(int u, int v){return !c[u] mi[v] - mi[u] de[v] - de[u];} // 判断 u - v 是否有红色节点。
LL dfs(int u) // 处理 ma ,K 和 L;
{ma[u] K[u] L[u] 0;if(dis[u]) ma[u] mi[u], (c[u] ? K[u] mi[u] : L[u] mi[u]); for(int i h[u]; ~i;i ne[i]){ma[u] max(ma[u], dfs(e[i])); K[u] max(K[u], K[e[i]]);in(u, e[i]) ? L[u] max(L[u], L[e[i]]) : K[u] max(K[u], L[e[i]]);}return ma[u];
}// 处理答案 k 是 以u为根的树之外的 节点的值 的 最大值;
// 那么 把 u 作为 红色节点的答案 max(k, max(K[u], L[u]-mi[i]));
LL df(int u, LL k)
{vectorLL v, m; for(int i h[u]; ~i;i ne[i])v.push_back(ma[e[i]]), m.push_back(ma[e[i]]);for(int i 1;i v.size();i ) v[i] max(v[i], v[i-1]);for(int i m.size()-2;i 0;i --) m[i] max(m[i], m[i1]); // 处理这棵树的前缀最大值和后缀最大值。int now 0;LL ans max(k, max(K[u], L[u]-mi[u]));for(int i h[u]; ~i;i ne[i]){LL tem k;if(dis[u]) tem max(tem, mi[u]);if(now ! v.size()-1) tem max(tem, m[now1]);if(now) tem max(tem, v[now-1]); ans min(ans, df(e[i], tem)); now;}h[u] -1;return ans;
}
stackint st;
LL build(int n) // 建立虚树
{st.push(1); idx 0;int tmp;for(int i 1;i n;i ){dis[a[i]] 1;if(a[i] 1) continue;int lc lca(a[i], st.top());while(lc ! st.top()){tmp st.top(); st.pop();if(dfn[st.top()] dfn[lc]) st.push(lc);add(st.top(), tmp, 0);}st.push(a[i]);}while(st.size() 1){tmp st.top(); st.pop();add(st.top(), tmp, 0);}st.pop();dfs(1);return df(1, 0);
}int main()
{int t;scanf(%d, t);while(t --){int n, m, q;scanf(%d%d%d, n, m, q);for(int i 1;i n;i ) h[i] -1; idx 0; cv 0;for(int i 1;i m;i ){int x;scanf(%d, x);c[x] 1;}for(int i 2;i n;i ){int u, v, w;scanf(%d%d%d, u, v, w);add(u, v, w); add(v, u, w);}dfs(1, 0);for(int i 1;i n;i ) h[i] -1;for(int _ 1;_ q;_ ){int k;scanf(%d, k);for(int i 1;i k;i ) scanf(%d, ai);sort(a1, ak1, cmp);printf(%lld\n, build(k));for(int i 1;i k;i ) dis[a[i]] 0;}for(int i 1;i n;i ) c[i] 0;}return 0;
}二分
int h[N], ne[N1], e[N1], w[N1], idx;
void add(int a, int b, int c){e[idx]b,ne[idx]h[a],w[idx]c,h[a]idx;return ;}int fa[N][20], deep[N], a[N];
LL mi[N], de[N];
bool c[N];void dfs(int u, int f)
{deep[u] deep[f] 1;for(int i 1;i 20;i ) fa[u][i] fa[fa[u][i-1]][i-1];for(int i h[u];~i ;i ne[i]){if(e[i] f)continue;fa[e[i]][0] u; mi[e[i]] c[e[i]] ? 0 : mi[u] w[i]; de[e[i]] de[u] w[i];dfs(e[i], u);}
}
int lca(int u, int v)
{if(deep[u]deep[v])swap(u, v);int x deep[u] - deep[v];for(int i 0;i 20;i )if(xi1)u fa[u][i];if(u v)return v;for(int i 19;i 0;i --)if(fa[u][i] ! fa[v][i])u fa[u][i], v fa[v][i];return fa[u][0];
}bool cmp(int u, int v){return mi[u] mi[v];}
bool in(int u, int v){return !c[u] mi[v]-mi[u] de[v] - de[u];} // 判断 u - v 是否有红色节点。
bool ch(LL t, int n)
{int now 0;for(int i 1;i n;i )if(mi[a[i]] t) now now ? lca(now, a[i]) : a[i];for(int i 1;i n;i )if(mi[a[i]] t)if(!in(now, a[i]) || mi[a[i]] - mi[now] t)return 0;return 1;
}int main()
{int t;scanf(%d, t);while(t --){int n, m, q;scanf(%d%d%d, n, m, q);for(int i 1;i n;i ) h[i] -1; idx 0; for(int i 1;i m;i ){int x;scanf(%d, x);c[x] 1;}for(int i 2;i n;i ){int u, v, w;scanf(%d%d%d, u, v, w);add(u, v, w); add(v, u, w);}dfs(1, 0);for(int _ 1;_ q;_ ){int k;scanf(%d, k);for(int i 1;i k;i ) scanf(%d, ai);sort(a1, ak1, cmp);LL l 0, r 1e17;while(l r)ch(mid, k) ? r mid : l mid1;printf(%lld\n, l);}for(int i 1;i n;i ) c[i] 0;}return 0;
}
