2.15 LCA

Nearest Common Ancestors POJ 1330

题意：给出一棵树， 询问两个点的最近公共祖先。

思路：

$LCA$模板题，请各位掏出各式各样的模板A穿它。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<queue>

 using namespace std;

 typedef long long ll;

 const int maxn = 1e4 + ;

 const int DEG = ;

 struct Edge {

     int to, nxt;

     Edge() {}

     Edge(int to, int nxt) :to(to), nxt(nxt) {}

 }edge[maxn << ];

 int head[maxn], tot;

 void Init()

 {

     tot = ;

     memset(head, -, sizeof head);

 }

 void addedge(int u, int v)

 {

     edge[tot] = Edge(v, head[u]); head[u] = tot++;

     edge[tot] = Edge(u, head[v]); head[v] = tot++;

 }

 int fa[maxn][DEG];

 int deg[maxn];

 void BFS(int root)

 {

     queue<int>q;

     deg[root] = ;

     fa[root][] = root;

     q.push(root);

     while (!q.empty())

     {

         int tmp = q.front();

         q.pop();

         for (int i = ; i < DEG; ++i)

         {

             fa[tmp][i] = fa[fa[tmp][i - ]][i - ];

         }

         for (int i = head[tmp]; i != -; i = edge[i].nxt)

         {

             int v = edge[i].to;

             if (v == fa[tmp][]) continue;

             deg[v] = deg[tmp] + ;

             fa[v][] = tmp;

             q.push(v);

         }

     }

 }

 int LCA(int u, int v)

 {

     if (deg[u] > deg[v]) swap(u, v);

     int hu = deg[u];

     int hv = deg[v];

     int tu = u, tv = v;

     for (int det = hv - hu, i = ; det; det >>= , ++i)

     {

         if (det & )

         {

             tv = fa[tv][i];

         }

     }

     if (tu == tv) return tu;

     for (int i = DEG - ; i >= ; --i)

     {

         if (fa[tu][i] == fa[tv][i])

             continue;

         tu = fa[tu][i];

         tv = fa[tv][i];

     }

     return fa[tu][];

 }

 int n;

 bool flag[maxn];

 void RUN()

 {

     int t;

     scanf("%d", &t);

     while (t--)

     {

         scanf("%d", &n);

         Init();

         memset(flag, false, sizeof flag);

         for (int i = ; i < n; ++i)

         {

             int u, v;

             ll w;

             scanf("%d %d", &u, &v);

             addedge(u, v);

             flag[v] = true;

         }

         int root = ;

         for (int i = ; i <= n; ++i)

         {

             if (!flag[i])

             {

                 root = i;

                 break;

             }

         }

         BFS(root);

         int u, v;

         scanf("%d %d", &u, &v);

         printf("%d\n", LCA(u, v));

     }

 }

 int main()

 {

 #ifdef LOCAL_JUDGE

     freopen("Text.txt", "r", stdin);

 #endif // LOCAL_JUDGE

     RUN();

 #ifdef LOCAL_JUDGE

     fclose(stdin);

 #endif // LOCAL_JUDGE

     return ;

 }

Closest Common Ancestors POJ 1470

题意：给出一棵树，然后给出几组询问，记录每个点作为询问中的最近公共祖先的次数并输出，如果次数为0则不输出。

思路：

$LCA$模板题，建图稍微注意一下后对于每次询问都记录他的最近最近公共祖先，输出。

 #include<cstdio>

 #include<iostream>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 using namespace std;

 typedef long long ll;

 const int maxn = 1e5 + ;

 const int DEG = ;

 struct Edge {

     int to, nxt;

     Edge() {}

     Edge(int to, int nxt) :to(to), nxt(nxt) {}

 }edge[maxn << ];

 int head[maxn], tot;

 int dis[maxn];

 void addedge(int u, int v)

 {

     edge[tot] = Edge(v, head[u]);

     head[u] = tot++;

 }

 void Init()

 {

     tot = ;

     memset(head, -, sizeof head);

 }

 int fa[maxn][DEG];

 int deg[maxn];

 void BFS(int root)

 {

     queue<int>q;

     deg[root] = ;

     fa[root][] = root;

     q.push(root);

     while (!q.empty())

     {

         int tmp = q.front();

         q.pop();

         for (int i = ; i < DEG; ++i)

         {

             fa[tmp][i] = fa[fa[tmp][i - ]][i - ];

         }

         for (int i = head[tmp]; i != -; i = edge[i].nxt)

         {

             int v = edge[i].to;

             if (v == fa[tmp][]) continue;

             deg[v] = deg[tmp] + ;

             fa[v][] = tmp;

             q.push(v);

         }

     }

 }

 int LCA(int u, int v)

 {

     if (deg[u] > deg[v]) swap(u, v);

     int hu = deg[u];

     int hv = deg[v];

     int tu = u, tv = v;

     for (int det = hv - hu, i = ; det; det >>= , ++i)

     {

         if (det & )

         {

             tv = fa[tv][i];

         }

     }

     if (tu == tv) return tu;

     for (int i = DEG - ; i >= ; --i)

     {

         if (fa[tu][i] == fa[tv][i])

             continue;

         tu = fa[tu][i];

         tv = fa[tv][i];

     }

     return fa[tu][];

 }

 int n, m;

 char str[maxn];

 bool flag[maxn];

 int arr[maxn];

 void RUN()

 {

     while (~scanf("%d", &n))

     {

         Init();

         memset(flag, false, sizeof flag);

         memset(arr, , sizeof arr);

         for (int i = ; i <= n; ++i)

         {

             int id, m;

             scanf("%d:(%d)", &id, &m);

             for (int i = ; i < m; ++i)

             {

                 int id2;

                 scanf("%d", &id2);

                 addedge(id, id2);

                 flag[id2] = true;

             }

         }

         int root = ;

         for (int i = ; i <= n; ++i)

         {

             if (!flag[i])

             {

                 root = i;

                 break;

             }

         }

         BFS(root);

         int q;

         scanf("%d", &q);

         while (q--)

         {

             int u, v;

             scanf(" (%d %d)", &u, &v);

             int root = LCA(u, v);

             arr[root]++;

         }

         for (int i = ; i <= n; ++i)

         {

             if (arr[i])

             {

                 printf("%d:%d\n", i, arr[i]);

             }

         }

     }

 }

 int main()

 {

 #ifdef LOCAL_JUDGE

     freopen("Text.txt", "r", stdin);

 #endif // LOCAL_JUDGE

     RUN();

 #ifdef LOCAL_JUDGE

     fclose(stdin);

 #endif // LOCAL_JUDGE

     return ;

 }

How far away ？HDU 2586

题意：给出一棵树，每条边有边权，然后给出几组询问，每组询问需要输出$u, v$之间的最短路径。

思路：

对于一棵树，两个点的路径唯一。

这两个点的路径长度为u到根的路径长度加上v到根的路径长度减去两倍LCA(u, v)到根的路径长度。

即$dis_u+dis_v-2 \cdot dis_{LCA_{u, v}}$。

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int maxn = 1e5 + ;

 const int DEG = ;

 int dis[maxn];

 struct Edge {

     int  to;

     int next;

     int w;

     Edge() {}

     Edge(int to, int next, int w) :to(to), next(next), w(w) {}

 }edge[maxn << ];

 int head[maxn];

 int tot;

 void addedge(int u, int v, int w)

 {

     edge[tot] = Edge(v, head[u], w);

     head[u] = tot++;

 }

 void init()

 {

     tot = ;

     memset(head, -, sizeof head);

     memset(dis, 0x3f, sizeof dis);

 }

 int fa[maxn][DEG];

 int deg[maxn];

 void BFS(int root)

 {

     queue<int>q;

     deg[root] = ;

     fa[root][] = root;

     q.push(root);

     dis[root] = ;

     while (!q.empty())

     {

         int tmp = q.front();

         q.pop();

         for (int i = ; i < DEG; ++i)

         {

             fa[tmp][i] = fa[fa[tmp][i - ]][i - ];

         }

         for (int i = head[tmp]; i != -; i = edge[i].next)

         {

             int v = edge[i].to;

             if (v == fa[tmp][]) continue;

             dis[v] = dis[tmp] + edge[i].w;

             deg[v] = deg[tmp] + ;

             fa[v][] = tmp;

             q.push(v);

         }

     }

 }

 int LCA(int u, int v)

 {

     if (deg[u] > deg[v])

         swap(u, v);

     int hu = deg[u], hv = deg[v];

     int tu = u;

     int tv = v;

     for (int det = hv - hu, i = ; det; det >>= , ++i)

     {

         if (det & )

         {

             tv = fa[tv][i];

         }

     }

     if (tu == tv) return tu;

     for (int i = DEG - ; i >= ; --i)

     {

         if (fa[tu][i] == fa[tv][i])

             continue;

         tu = fa[tu][i];

         tv = fa[tv][i];

     }

     return fa[tu][];

 }

 void RUN()

 {

     int t;

     scanf("%d", &t);

     while (t--)

     {

         init();

         int n, q;

         scanf("%d %d", &n, &q);

         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);

         }

         BFS();

         while (q--)

         {

             int u, v;

             scanf("%d %d", &u, &v);

             int root = LCA(u, v);

             int ans = dis[u] + dis[v] -  * dis[root];

             printf("%d\n", ans);

         }

     }

 }

 int main()

 {

 #ifdef LOCAL_JUDGE

     freopen("Text.txt", "r", stdin);

 #endif // LOCAL_JUDGE

     RUN();

 #ifdef LOCAL_JUDGE

     fclose(stdin);

 #endif // LOCAL_JUDGE

     return ;

 }

Connections between cities HDU 2874

题意：给出一张图，保证无环，但是不保证连通，求出两个点的最短距离，如果不连通就输出$"Not connected"$。

思路：

由于保证无环，那么给出的图就是一颗或者多颗树。

那么可以用并查集来维护两点是否在一个集合中，也就是一棵树中。

对于在一棵树上的$u,v$两点，距离就是$dis_u+dis_v-2 \cdot dis_{LCA_{u, v}}$。

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int maxn = 1e5 + ;

 const int DEG = ;

 int n, m, q;

 int Fa[maxn];

 int dis[maxn];

 int find(int x)

 {

     return x == Fa[x] ? Fa[x] : Fa[x] = find(Fa[x]);

 }

 void mix(int x, int y)

 {

     x = find(x);

     y = find(y);

     if (x != y)

     {

         Fa[x] = y;

     }

 }

 struct Edge {

     int  to;

     int next;

     int w;

     Edge() {}

     Edge(int to, int next, int w) :to(to), next(next), w(w) {}

 }edge[maxn << ];

 int head[maxn];

 int tot;

 void addedge(int u, int v, int w)

 {

     edge[tot] = Edge(v, head[u], w);

     head[u] = tot++;

 }

 void init()

 {

     tot = ;

     memset(head, -, sizeof head);

     memset(dis, , sizeof dis);

     for (int i = ; i <= n; ++i)

     {

         Fa[i] = i;

     }

 }

 int fa[maxn][DEG];

 int deg[maxn];

 void BFS()

 {

     queue<int>q;

     for (int i = ; i <= n; ++i)

     {

         if (find(i) == i)

         {

             deg[i] = ;

             fa[i][] = i;

             dis[i] = ;

             q.push(i);

         }

     }

     while (!q.empty())

     {

         int tmp = q.front();

         q.pop();

         for (int i = ; i < DEG; ++i)

         {

             fa[tmp][i] = fa[fa[tmp][i - ]][i - ];

         }

         for (int i = head[tmp]; i != -; i = edge[i].next)

         {

             int v = edge[i].to;

             if (v == fa[tmp][]) continue;

             dis[v] = dis[tmp] + edge[i].w;

             deg[v] = deg[tmp] + ;

             fa[v][] = tmp;

             q.push(v);

         }

     }

 }

 int LCA(int u, int v)

 {

     if (deg[u] > deg[v])

         swap(u, v);

     int hu = deg[u], hv = deg[v];

     int tu = u;

     int tv = v;

     for (int det = hv - hu, i = ; det; det >>= , ++i)

     {

         if (det & )

         {

             tv = fa[tv][i];

         }

     }

     if (tu == tv) return tu;

     for (int i = DEG - ; i >= ; --i)

     {

         if (fa[tu][i] == fa[tv][i])

             continue;

         tu = fa[tu][i];

         tv = fa[tv][i];

     }

     return fa[tu][];

 }

 void solve()

 {

     int u, v;

     scanf("%d %d", &u, &v);

     int rootu = find(u);

     int rootv = find(v);

     if (rootu != rootv)

     {

         puts("Not connected");

         return;

     }

     int root = LCA(u, v);

     int ans = dis[u] + dis[v] -  * dis[root];

     printf("%d\n", ans);

 }

 void RUN()

 {

     while (~scanf("%d %d %d", &n, &m, &q))

     {

         init();

         for (int i = ; i < m; ++i)

         {

             int u, v, w;

             scanf("%d %d %d", &u, &v, &w);

             addedge(u, v, w);

             addedge(v, u, w);

             mix(u, v);

         }

         BFS();

         while (q--)

         {

             solve();

         }

     }

 }

 int main()

 {

 #ifdef LOCAL_JUDGE

     freopen("Text.txt", "r", stdin);

 #endif // LOCAL_JUDGE

     RUN();

 #ifdef LOCAL_JUDGE

     fclose(stdin);

 #endif // LOCAL_JUDGE

     return ;

 }

Network POJ - 3417

题意：给出一棵树和一些非树边，你可以选择破坏一条树边以及一条非树边，问有多少种方式可以破坏这棵树。

思路：

对于每条非树边$u-v$都可以形成一个$u-LCA_{u, v}-v-u$的环，如果破坏这个这个环则只能选择环上一个树边以及新加入的非树边。

如果某条树边被多个环覆盖那么无法通过破坏这条边以及非树边来破坏整棵树。

如果某条树边没有被环覆盖那么可以通过破坏这条树边以及任意一条非树边来破坏整棵树。

最后可以通过$LCA$以及树上差分(前缀和？)来优化求出每条树边被多少个环覆盖。

 #include<cstdio>

 #include<iostream>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 using namespace std;

 typedef long long ll;

 const int maxn = 1e6 + ;

 const int DEG = ;

 struct Edge {

     int to, nxt;

     Edge() {}

     Edge(int to, int nxt) :to(to), nxt(nxt) {}

 }edge[maxn << ];

 int head[maxn], tot;

 int dis[maxn];

 void addedge(int u, int v)

 {

     edge[tot] = Edge(v, head[u]);

     head[u] = tot++;

 }

 void init()

 {

     memset(head, -, sizeof head);

     tot = ;

 }

 int fa[maxn][DEG];

 int deg[maxn];

 void BFS(int root)

 {

     queue<int>q;

     deg[root] = ;

     fa[root][] = root;

     q.push(root);

     while (!q.empty())

     {

         int tmp = q.front();

         q.pop();

         for (int i = ; i < DEG; ++i)

         {

             fa[tmp][i] = fa[fa[tmp][i - ]][i - ];

         }

         for (int i = head[tmp]; i != -; i = edge[i].nxt)

         {

             int v = edge[i].to;

             if (v == fa[tmp][]) continue;

             deg[v] = deg[tmp] + ;

             fa[v][] = tmp;

             q.push(v);

         }

     }

 }

 int LCA(int u, int v)

 {

     if (deg[u] > deg[v]) swap(u, v);

     int hu = deg[u];

     int hv = deg[v];

     int tu = u, tv = v;

     for (int det = hv - hu, i = ; det; det >>= , ++i)

     {

         if (det & )

         {

             tv = fa[tv][i];

         }

     }

     if (tu == tv) return tu;

     for (int i = DEG - ; i >= ; --i)

     {

         if (fa[tu][i] == fa[tv][i])

             continue;

         tu = fa[tu][i];

         tv = fa[tv][i];

     }

     return fa[tu][];

 }

 int n, m;

 ll arr[maxn];

 void DFS(int u, int pre)

 {

     for (int i = head[u]; ~i; i = edge[i].nxt)

     {

         int v = edge[i].to;

         if (v == pre) continue;

         DFS(v, u);

         arr[u] += arr[v];

     }

 }

 void RUN()

 {

     while (~scanf("%d %d", &n, &m))

     {

         init();

         memset(arr, , sizeof arr);

         for (int i = ; i < n; ++i)

         {

             int u, v;

             scanf("%d %d", &u, &v);

             addedge(u, v);

             addedge(v, u);

         }

         BFS();

         for (int i = ; i <= m; ++i)

         {

             int u, v;

             scanf("%d %d", &u, &v);

             arr[u]++;

             arr[v]++;

             arr[LCA(u, v)] -= ;

         }

         DFS(, -);

         ll ans = ;

         for (int i = ; i <= n; ++i)

         {

             if (!arr[i])

             {

                 ans += m;

             }

             else if (arr[i] == )

             {

                 ans++;

             }

         }

         printf("%lld\n", ans);

     }

 }

 int main()

 {

 #ifdef LOCAL_JUDGE

     freopen("Text.txt", "r", stdin);

 #endif // LOCAL_JUDGE

     RUN();

 #ifdef LOCAL_JUDGE

     fclose(stdin);

 #endif // LOCAL_JUDGE

     return ;

 }

Imperial roads UVALive - 8196

题意：给出一张图，然后询问给出一条边，求有这条边的最小生成树的权值和。

思路：

先求最小生成树，然后询问的边如果在最小生成树里面那么就是原来的最小生成树的权值和。

否则在原来的最小生成树里面的加入一条边，形成个环，然后去掉这个环里面除了加入的边之外的边权最大的边即可。

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int maxn = 2e5 + ;

 const int DEG = ;

 int n, m;

 struct node {

     int u, v;

     ll w;

     node() {}

     node(int u, int v, ll w) :u(u), v(v), w(w) {}

     inline bool operator < (const node &b)const

     {

         return w < b.w;

     }

 };

 struct Edge {

     int to;

     int nxt;

     ll w;

     Edge() {}

     Edge(int to, int nxt, ll w) :to(to), nxt(nxt), w(w) {}

 }edge[maxn << ];

 int dis[maxn][DEG];

 bool inMST[maxn << ];

 int head[maxn];

 int tot;

 int father[maxn];

 vector<node>G;

 int cnt;

 map<pair<int, int>, int>mp;

 void addedge(int u, int v, ll w)

 {

     edge[tot] = Edge(v, head[u], w); head[u] = tot++;

     edge[tot] = Edge(u, head[v], w); head[v] = tot++;

 }

 void Init()

 {

     G.clear();

     cnt = ;

     tot = ;

     memset(dis, , sizeof dis);

     memset(head, -, sizeof head);

     for (int i = ; i <= n; ++i)

     {

         father[i] = i;

     }

 }

 int find(int x)

 {

     return x == father[x] ? father[x] : father[x] = find(father[x]);

 }

 void mix(int x, int y)

 {

     x = find(x);

     y = find(y);

     if (x != y)

     {

         father[x] = y;

     }

 }

 bool same(int x, int y)

 {

     return find(x) == find(y);

 }

 ll MST()

 {

     mp.clear();

     ll res = ;

     sort(G.begin(), G.end());

     memset(inMST, false, sizeof inMST);

     for (auto it : G)

     {

         int u = it.u;

         int v = it.v;

         mp[make_pair(v, u)] = cnt;

         mp[make_pair(u, v)] = cnt++;

     }

     for (auto it : G)

     {

         int u = it.u;

         int v = it.v;

         if (same(u, v)) continue;

         mix(u, v);

         inMST[mp[make_pair(u, v)]] = true;

         addedge(u, v, it.w);

         res += it.w;

     }

     return res;

 }

 int fa[maxn][DEG];

 int deg[maxn];

 void BFS(int root)

 {

     queue<int>q;

     deg[root] = ;

     fa[root][] = root;

     q.push(root);

     while (!q.empty())

     {

         int tmp = q.front();

         q.pop();

         for (int i = ; i < DEG; ++i)

         {

             dis[tmp][i] = max(dis[tmp][i - ], dis[fa[tmp][i - ]][i - ]);

             fa[tmp][i] = fa[fa[tmp][i - ]][i - ];

         }

         for (int i = head[tmp]; ~i; i = edge[i].nxt)

         {

             int v = edge[i].to;

             if (v == fa[tmp][]) continue;

             deg[v] = deg[tmp] + ;

             fa[v][] = tmp;

             int id = mp[make_pair(tmp, v)];

             dis[v][] = G[id].w;

             q.push(v);

         }

     }

 }

 int LCA(int u, int v)

 {

     int res = ;

     if (deg[u] > deg[v])

         swap(u, v);

     int hu = deg[u], hv = deg[v];

     int tu = u, tv = v;

     for (int det = hv - hu, i = ; det; det >>= , ++i)

     {

         if (det & )

         {

             res = max(res, dis[tv][i]);

             tv = fa[tv][i];

         }

     }

     if (tu == tv) return res;

     for (int i = DEG - ; i >= ; --i)

     {

         if (fa[tu][i] == fa[tv][i]) continue;

         res = max(res, max(dis[tu][i], dis[tv][i]));

         tu = fa[tu][i];

         tv = fa[tv][i];

     }

     res = max(res, max(dis[tu][], dis[tv][]));

     return res;

 }

 void RUN()

 {

     while (~scanf("%d %d", &n, &m))

     {

         Init();

         for (int i = ; i <= m; ++i)

         {

             int u, v;

             ll w;

             scanf("%d %d %lld", &u, &v, &w);

             G.push_back(node(u, v, w));

         }

         ll ans = MST();

         BFS();

         int q;

         scanf("%d", &q);

         while (q--)

         {

             int u, v;

             scanf("%d %d", &u, &v);

             int id = mp[make_pair(u, v)];

             ll w = G[id].w;

             if (inMST[id])

             {

                 printf("%lld\n", ans);

             }

             else

             {

                 ll res = LCA(u, v);

                 printf("%lld\n", ans + w - res);

             }

         }

     }

 }

 int main()

 {

 #ifdef LOCAL_JUDGE

     freopen("Text.txt", "r", stdin);

 #endif // LOCAL_JUDGE

     RUN();

 #ifdef LOCAL_JUDGE

     fclose(stdin);

 #endif // LOCAL_JUDGE

     return ;

 }

CD操作 HDU - 4547

题意：

思路：

从$u-v$的操作数为$dis_u-dis_{LCA{u, v}}$

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int maxn = 1e5 + ;

 const int DEG = ;

 struct Edge {

     int to, nxt;

     inline Edge() {}

     inline Edge(int to, int nxt) :to(to), nxt(nxt) {}

 }edge[maxn << ];

 int head[maxn], tot;

 map<string, int>mp;

 int dis[maxn];

 inline void addedge(int u, int v)

 {

     edge[tot] = Edge(v, head[u]);

     head[u] = tot++;

 }

 inline void init()

 {

     memset(head, -, sizeof head);

     tot = ;

 }

 int fa[maxn][DEG];

 int deg[maxn];

 inline void BFS(int root)

 {

     queue<int>q;

     deg[root] = ;

     dis[root] = ;

     fa[root][] = root;

     q.push(root);

     while (!q.empty())

     {

         int tmp = q.front();

         q.pop();

         for (int i = ; i < DEG; ++i)

         {

             fa[tmp][i] = fa[fa[tmp][i - ]][i - ];

         }

         for (int i = head[tmp]; i != -; i = edge[i].nxt)

         {

             int v = edge[i].to;

             if (v == fa[tmp][]) continue;

             deg[v] = deg[tmp] + ;

             dis[v] = dis[tmp] + ;

             fa[v][] = tmp;

             q.push(v);

         }

     }

 }

 inline int LCA(int u, int v)

 {

     if (deg[u] > deg[v]) swap(u, v);

     int hu = deg[u];

     int hv = deg[v];

     int tu = u, tv = v;

     for (int det = hv - hu, i = ; det; det >>= , ++i)

     {

         if (det & )

         {

             tv = fa[tv][i];

         }

     }

     if (tu == tv) return tu;

     for (int i = DEG - ; i >= ; --i)

     {

         if (fa[tu][i] == fa[tv][i])

             continue;

         tu = fa[tu][i];

         tv = fa[tv][i];

     }

     return fa[tu][];

 }

 int n, m;

 bool flag[maxn];

 inline void RUN()

 {

     int t;

     cin >> t;

     while (t--)

     {

         cin >> n >> m;

         init();

         mp.clear();

         int cnt = ;

         memset(flag, false, sizeof flag);

         for (int i = ; i < n; ++i)

         {

             string s1, s2;

             cin >> s1 >> s2;

             if (mp[s1] == )

             {

                 mp[s1] = cnt++;

             }

             if (mp[s2] == )

             {

                 mp[s2] = cnt++;

             }

             addedge(mp[s2], mp[s1]);

             addedge(mp[s1], mp[s2]);

             flag[mp[s1]] = true;

         }

         int root = ;

         for (int i = ; i < cnt; ++i)

         {

             if (!flag[i])

             {

                 root = i;

                 break;

             }

         }

         BFS(root);

         while (m--)

         {

             string s1, s2;

             cin >> s1 >> s2;

             int u = mp[s1];

             int v = mp[s2];

             int tmp = LCA(u, v);

             int ans = dis[u] - dis[tmp];

             if (tmp != v)

             {

                 ans++;

             }

             cout << ans << endl;

         }

     }

 }

 int main()

 {

 #ifdef LOCAL_JUDGE

     freopen("Text.txt", "r", stdin);

 #endif // LOCAL_JUDGE

     RUN();

 #ifdef LOCAL_JUDGE

     fclose(stdin);

 #endif // LOCAL_JUDGE

     return ;

 }

Red Black Tree ZOJ - 4048

题意：有一个树，上面有红点和黑点，有边权，每个点的花费定义为它到离它最近的红点的距离，每次询问给出一些点，能够将这棵树中的一个黑点变为红点，使得这些点中的最大花费最小

思路：

二分答案，符合条件的点不管，将不符合条件的点LCA求出来，变红，然后算距离

ST表求LCA可直接过，复杂度为$O(n \cdot log_n)$。

倍增求LCA复杂度为$O(n \cdot log_n \cdot log_n)$。

倍增求LCA可先根据深度排序，当有两个不符合的点上方的红点不同时则不能通过修改一个点使得所有不符合的点都产生改变，从而剪枝。

ST表。

 #include <bits/stdc++.h>

 using namespace std;

 #define N 100010

 #define ll long long

 #define INFLL 0x3f3f3f3f3f3f3f3f

 struct Edge

 {

     int to, nx; ll w;

     inline Edge() {}

     inline Edge(int to, int nx, ll w) : to(to), nx(nx), w(w) {}

 }edge[N << ];

 int t, n, m, q, k;

 int isred[N], prered[N], head[N], arr[N], pos;

 int rmq[N << ], F[N << ], P[N], deep[N], cnt;

 ll dist[N]; 

 inline void Init()

 {

     memset(head, -, sizeof head); pos = ;

     memset(isred, , sizeof isred);  deep[] = ;

 }

 inline void addedge(int u, int v, ll w)

 {

     edge[++pos] = Edge(v, head[u], w); head[u] = pos;

 }

 struct ST

 {

     int mm[N << ];

     int dp[N << ][];

     inline void init(int n)

     {

         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)

             {

                 dp[i][j] = rmq[dp[i][j - ]] < rmq[dp[i + ( << (j - ))][j - ]] ? dp[i][j - ] : dp[i + ( << (j - ))][j - ];

             }

         }

     }

     inline int query(int a, int b)

     {

         if (a > b) swap(a, b);

         int k = mm[b - a + ];

         return rmq[dp[a][k]] <= rmq[dp[b - ( << k) + ][k]] ? dp[a][k] : dp[b - ( << k) + ][k];

     }

 }st;

 inline void DFS(int u, int pre, int prer)

 {

     F[++cnt] = u;

     rmq[cnt] = deep[u];

     P[u] = cnt;

     prered[u] = prer;

     for (int it = head[u]; ~it; it = edge[it].nx)

     {

         int v = edge[it].to;

         if (v == pre) continue;

         if (isred[v]) dist[v] = ;

         else dist[v] = dist[u] + edge[it].w;

         deep[v] = deep[u] + ;

         DFS(v, u, isred[v] ? v : prer);

         F[++cnt] = u;

         rmq[cnt] = deep[u];

     }

 }

 inline void Lca_Init(int root, int node_num)

 {

     cnt = ;

     DFS(root, root, );

     st.init( * node_num - );

 }

 inline int query_lca(int u, int v)

 {

     return F[st.query(P[u], P[v])];

 }

 vector <int> v;

 inline bool check(ll mid)

 {

     v.clear();

     for (int i = ; i <= k; ++i)

     {

         if (dist[arr[i]] > mid)

             v.emplace_back(arr[i]);

     }

     if (v.empty()) return true;

     int lca = v[];

     for (int i = , len = v.size(); i < len; ++i)

         lca = query_lca(lca, v[i]);

     if (isred[lca]) return false;

     for (auto it : v)

     {

         if (deep[lca] < deep[prered[it]]) return false;

         else if (dist[it] - dist[lca] > mid) return false;

     }

     return true;

 }

 inline void Run()

 {

     for (scanf("%d", &t); t--; )

     {

         scanf("%d%d%d", &n, &m, &q); Init();

         for (int i = , u; i <= m; ++i)

         {

             scanf("%d", &u);

             isred[u] = ;

         }

         ll w;

         for (int i = , u, v; i < n; ++i)

         {

             scanf("%d%d%lld", &u, &v, &w);

             addedge(u, v, w); addedge(v, u, w);

         }

         Lca_Init(, n);

         for (int qq = ; qq <= q; ++qq)

         {

             scanf("%d", &k);

             for (int i = ; i <= k; ++i) scanf("%d", arr + i);

             if (k == )

             {

                 puts("");

                 continue;

             }

             ll l = , r = INFLL, ans;

             while (r - l >= )

             {

                 ll mid = (l + r) >> ;

                 if (check(mid))

                 {

                     ans = mid;

                     r = mid - ;

                 }

                 else

                     l = mid + ;

             }

             printf("%lld\n", ans);

         }

     }

 }

 int main()

 {

     #ifdef LOCAL

         freopen("Test.in", "r", stdin);

     #endif    

     Run();

     return ;

 }

倍增求LCA。

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int INF = 0x3f3f3f3f;

 const ll INFLL = 0x3f3f3f3f3f3f3f3f;

 const ll MOD = (int)1e9 + ;

 const int maxn = (int)1e5 + ;

 const int DEG = ;

 struct Edge {

     int to, nxt;

     ll w;

     Edge() {}

     Edge(int to, int nxt, ll w) :to(to), nxt(nxt), w(w) {}

 }edge[maxn << ];

 int head[maxn], tot;

 int red[maxn];

 void addedge(int u, int v, ll w)

 {

     edge[tot] = Edge(v, head[u], w); head[u] = tot++;

 }

 void Init(int n)

 {

     for (int i = ; i <= n; ++i)

     {

         red[i] = ;

         head[i] = -;

     }

     tot = ;

 }

 ll dis[maxn];

 int fa[maxn][DEG];

 int deg[maxn];

 int pre[maxn];

 void BFS(int root)

 {

     queue<int>q;

     dis[root] = ;

     deg[root] = ;

     fa[root][] = root;

     pre[root] = root;

     q.push(root);

     while (!q.empty())

     {

         int tmp = q.front();

         q.pop();

         for (int i = ; i < DEG; ++i)

         {

             fa[tmp][i] = fa[fa[tmp][i - ]][i - ];

         }

         for (int i = head[tmp]; ~i; i = edge[i].nxt)

         {

             int v = edge[i].to;

             ll w = edge[i].w;

             if (v == fa[tmp][]) continue;

             deg[v] = deg[tmp] + ;

             fa[v][] = tmp;

             if (red[v])

             {

                 pre[v] = v;

             }

             else

             {

                 pre[v] = pre[tmp];

             }

             if (red[v])

             {

                 dis[v] = ;

             }

             else

             {

                 dis[v] = dis[tmp] + w;

             }

             q.push(v);

         }

     }

 }

 int LCA(int u, int v)

 {

     if (deg[u] > deg[v]) swap(u, v);

     int hu = deg[u], hv = deg[v];

     int tu = u, tv = v;

     for (int det = hv - hu, i = ; det; det >>= , ++i)

     {

         if (det & )

         {

             tv = fa[tv][i];

         }

     }

     if (tu == tv) return tu;

     for (int i = DEG - ; i >= ; --i)

     {

         if (fa[tu][i] == fa[tv][i]) continue;

         tu = fa[tu][i], tv = fa[tv][i];

     }

     return fa[tu][];

 }

 int n, m, q, k;

 int arr[maxn];

 bool cmp(int a, int b)

 {

     return dis[a] > dis[b];

 }

 bool check(ll mid)

 {

     int root = arr[];

     int cnt = ;

     for (int i = ; i <= k; ++i)

     {

         if (dis[arr[i]] > mid)

         {

             if (pre[root] != pre[arr[i]]) return false;

             root = LCA(root, arr[i]);

             cnt++;

         }

     }

     if (cnt ==  || cnt == ) return true;

     for (int i = ; i <= k; ++i)

     {

         if (dis[arr[i]] > mid)

         {

             if (dis[arr[i]] - dis[root] > mid) return false;

         }

     }

     return true;

 }

 void RUN()

 {

     int t;

     scanf("%d", &t);

     while (t--)

     {

         scanf("%d %d %d", &n, &m, &q);

         Init(n);

         for (int i = ; i <= m; ++i)

         {

             int u;

             scanf("%d", &u);

             red[u] = ;

         }

         for (int i = ; i < n; ++i)

         {

             int u, v;

             ll w;

             scanf("%d %d %lld", &u, &v, &w);

             addedge(u, v, w);

             addedge(v, u, w);

         }

         BFS();

         while (q--)

         {

             scanf("%d", &k);

             for (int i = ; i <= k; ++i)

             {

                 scanf("%d", arr + i);

             }

             if (k == )

             {

                 puts("");

                 continue;

             }

             sort(arr + , arr +  + k, cmp);

             ll l = ;

             ll r = INFLL;

             ll ans = ;

             while (r - l >= )

             {

                 ll mid = (r + l) >> ;

                 if (check(mid))

                 {

                     r = mid - ;

                     ans = mid;

                 }

                 else

                 {

                     l = mid + ;

                 }

             }

             printf("%lld\n", ans);

         }

     }

 }

 int main()

 {

 #ifdef LOCAL_JUDGE

     freopen("Text.txt", "r", stdin);

 #endif // LOCAL_JUDGE

     RUN();

 #ifdef LOCAL_JUDGE

     fclose(stdin);

 #endif // LOCAL_JUDGE

     return ;

 }

最新文章

  1. UDP Server
  2. HTTP 错误 500.21 - Internal Server Error 解决方案
  3. 封锁Skype的广告(非原创)
  4. symonfy 项目根目录下没有 bin/console 文件的解决方法
  5. AWS ElastiCache 使用笔记
  6. Python 学习入门（23）—— 进程
  7. winform的Textbox设置只读之后ForeColor无效的解决方法
  8. 分析easyswoole3.0源码，Trace组件（四）
  9. django在关闭debug后，admin界面 及静态文件无法加载的解决办法
  10. 我的IT之路这样走过
  11. html 框架 內聯框架
  12. Expm 4_2 有向无环图中的最短路径问题
  13. qrcodebox 面向移动设备的二维码弹出框
  14. 【Linux学习五】文本处理
  15. python的类和对象
  16. c语言中条件编译相关的预编译指令
  17. SecureCRT来上传和下载文件
  18. 3D Spherical Geometry Kernel( Geometry Kernels） CGAL 4.13 -User Manual
  19. JavaScript初学者福利！必须收藏的24条小技巧
  20. undefined vs. null

热门文章

  1. 【数据结构】P1981 表达式求值
  2. Scratch教程：谁是真悟空
  3. hdu 4857 反向拓扑问题
  4. vue学习（4）-组件的创建，父子组件传值，$refs
  5. jq 停止/结束多个ajax请求
  6. CSS3自定义滚动条样式方法
  7. JAVA面试核心教程｜Java面试基础知识点总结
  8. trape 一种识别工具
  9. IDEA 导入jar包
  10. 第二章 Django之Django安装（2）