HDU 5150 UVALive 5061 (LCA标记)

2024-08-24 11:58
文章标签 标记 lca hdu uvalive 5150 5061

本文主要是介绍HDU 5150 UVALive 5061 (LCA标记)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这两题都是在树上求某一些路径上的点权的变化

两道题的思路相同

HDU 5150：

每一种颜色我们分开考虑他们对所有节点的贡献，对于颜色同为c的两个节点u和v(假设u!=v)，那么在lca(u,v)的时候我们需要-1，因为在lca(u,v)一直到根的路径上，颜色c只能影响一次。基于此，我们对每种颜色的所有节点按照dfs序排好序，首先每个节点+1，然后对dfs序相邻的两个节点（注意颜色要相同）求一次lca，在lca这个位置-1，最后dfs一次将儿子的贡献累加上来就得到了每种颜色对自己的贡献了。

//      whn6325689
//		Mr.Phoebe
//		http://blog.csdn.net/u013007900
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#include <functional>
#include <numeric>
#pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef complex<ld> point;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef vector<int> vi;#define CLR(x,y) memset(x,y,sizeof(x))
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define lowbit(x) (x&(-x))
#define MID(x,y) (x+((y-x)>>1))
#define eps 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LLINF 1LL<<62template<class T>
inline bool read(T &n)
{T x = 0, tmp = 1; char c = getchar();while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();if(c == EOF) return false;if(c == '-') c = getchar(), tmp = -1;while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();n = x*tmp;return true;
}
template <class T>
inline void write(T n)
{if(n < 0){putchar('-');n = -n;}int len = 0,data[20];while(n){data[len++] = n%10;n /= 10;}if(!len) data[len++] = 0;while(len--) putchar(data[len]+48);
}
//-----------------------------------
const int MAXN=50010;
const int MAXM=100010;struct Edge
{int to,next;
}e[2100005];int head[MAXN],tail[MAXN],tot;
int n,m,num[MAXN];
int fa[MAXN];
vector<int> a[MAXN];
vector<int> b[MAXM];int findfa(int x)
{return fa[x]==x?x:fa[x]=findfa(fa[x]);
}inline void merge(int u,int v)
{int t1=findfa(u);int t2=findfa(v);if(t1!=t2)fa[u]=v;
}void init()
{tot=0;CLR(head,-1);CLR(tail,-1);CLR(num,0);for(int i=0;i<=n;i++)fa[i]=i,a[i].clear();
}void addedge(int u,int v,int* head)
{e[tot].to=v;e[tot].next=head[u];head[u]=tot++;
}void LCA(int u=1,int fa=-1)
{for(int i=head[u];~i;i=e[i].next){int v=e[i].to;if(v==fa)	continue;LCA(v,u);merge(v,u);}for(int i=tail[u];~i;i=e[i].next){num[findfa(e[i].to)]--;}
}void dfs(int u=1,int fa=-1)
{int sz=a[u].size();for(int i=0;i<sz;i++)b[a[u][i]].pb(u);for(int i=head[u];~i;i=e[i].next){int v=e[i].to;if(v==fa)	continue;dfs(v,u);}
}int calc(int u=1,int fa=-1)
{for(int i=head[u];~i;i=e[i].next){int v=e[i].to;if(v==fa)	continue;num[u]+=calc(v,u);}return num[u];
}int main()
{while(read(n)&&read(m)){init();for(int i=1,u,v;i<n;i++){read(u),read(v);addedge(u,v,head);addedge(v,u,head);}int maxx=-1;for(int i=0,u,v;i<m;i++){read(u),read(v);a[u].pb(v);maxx=max(maxx,v);}dfs();for(int i=1;i<=maxx;i++){int sz=b[i].size();if(!sz)	continue;else if(sz==1)num[b[i][0]]++;else{int pre=b[i][0];num[pre]++;for(int j=1;j<sz;j++){int v=b[i][j];addedge(v,pre,tail);num[v]++;pre=v;}}b[i].clear();}LCA();calc();for(int i=1;i<=n;i++)printf("%d%c",num[i],i==n?'\n':' ');}return 0;
}



UVALive 5061

考虑树上u,v两点之间的路径，必定经过LCA(u,v)，那么LCA(u,v)的祖先就不会受到影响，但是LCA(u,v)自己应该受到一次影响

如果按照dfs，将子孙的贡献值全部累加上了，u和v通往LCA(u,v)的路径上各个点会受到一次影响，但是LCA(u,v)会受到两次影响，因此LCA(u,v)必须标记负的权值(-w)，这样LCA(u,v)以及其祖先都会受到一次影响，那么我们需要在LCA(u,v)的father上面再一次标记负的权值(-w)，因此当贡献值累加到LCA(u,v)的father的时候，影响就会被消除，从而满足贡献值的分配

<span style="font-size:18px;">//      whn6325689
//		Mr.Phoebe
//		http://blog.csdn.net/u013007900
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#include <functional>
#include <numeric>
#pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef complex<ld> point;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef vector<int> vi;#define CLR(x,y) memset(x,y,sizeof(x))
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define lowbit(x) (x&(-x))
#define MID(x,y) (x+((y-x)>>1))
#define eps 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LLINF 1LL<<62template<class T>
inline bool read(T &n)
{T x = 0, tmp = 1; char c = getchar();while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();if(c == EOF) return false;if(c == '-') c = getchar(), tmp = -1;while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();n = x*tmp;return true;
}
template <class T>
inline void write(T n)
{if(n < 0){putchar('-');n = -n;}int len = 0,data[20];while(n){data[len++] = n%10;n /= 10;}if(!len) data[len++] = 0;while(len--) putchar(data[len]+48);
}
//-----------------------------------const int MAXN=50010;
const int DEG=20;struct Edge
{int to,next;
}e[MAXN*2];
int head[MAXN],tot;void addedge(int u,int v)
{e[tot].to=v;e[tot].next=head[u];head[u]=tot++;e[tot].to=u;e[tot].next=head[v];head[v]=tot++;
}void init()
{tot=0;CLR(head,-1);
}int fa[MAXN][DEG];
int deg[MAXN];void bfs(int root=0)
{queue<int> q;deg[root]=0;fa[root][0]=root;q.push(root);while(!q.empty()){int tmp=q.front();q.pop();for(int i=1;i<DEG;i++)fa[tmp][i]=fa[fa[tmp][i-1]][i-1];for(int i=head[tmp];~i;i=e[i].next){int v=e[i].to;if(v==fa[tmp][0])	continue;deg[v]=deg[tmp]+1;fa[v][0]=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,tv=v;for(int det=hv-hu,i=0;det;det>>=1,i++)if(det&1)tv=fa[tv][i];if(tu==tv)	return tu;for(int i=DEG-1;i>=0;i--){if(fa[tu][i]==fa[tv][i])continue;tu=fa[tu][i];tv=fa[tv][i];}return fa[tu][0];
}int val[MAXN];void dfs(int u,int fa=-1)
{int ret=val[u];for(int i=head[u];~i;i=e[i].next){int v=e[i].to;if(v==fa)continue;dfs(v,u);ret+=val[v];}val[u]=ret;
}int main()
{int T,n,m,cas=1;read(T);while(T--){init();printf("Case #%d:\n",cas++);read(n);for(int i=0,u,v;i<n-1;i++){read(u),read(v);addedge(u,v);}bfs(0);CLR(val,0);read(m);for(int i=0,u,v,w;i<m;i++){read(u),read(v),read(w);val[u]+=w;val[v]+=w;int lca=LCA(u,v);val[lca]-=w;if(lca)val[fa[lca][0]]-=w;}dfs(0);for(int i=0;i<n;i++)write(val[i]),putchar('\n');}return 0;
}
</span>

这篇关于HDU 5150 UVALive 5061 (LCA标记)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1102418。

相关文章

poj1330（LCA最近公共祖先）

poj1330（LCA最近公共祖先）

题意：求最近公共祖先 思路：之前学习了树链剖分，然后我就用树链剖分的一小部分知识就可以解这个题目了，记录每个结点的fa和depth。然后查找时，每次将depth大的结点往上走直到x = y。 代码如下： #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring>
阅读更多...
usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心： 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数，若返回值为正，qsort 函数判定a>b ；为负，a<b；为0，a==b； int milkcmp(const void *va,c
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...
hdu 2093 考试排名（sscanf）

hdu 2093 考试排名（sscanf）

模拟题。 直接从教程里拉解析。 因为表格里的数据格式不统一。有时候有"()"，有时候又没有。而它也不会给我们提示。 这种情况下，就只能它它们统一看作字符串来处理了。现在就请出我们的主角sscanf()! sscanf 语法: #include int sscanf( const char *buffer, const char *format, ... ); 函数sscanf()和
阅读更多...
hdu 2602 and poj 3624(01背包)

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码： #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s
阅读更多...
hdu 1754 I Hate It（线段树，单点更新，区间最值）

hdu 1754 I Hate It（线段树，单点更新，区间最值）

题意是求一个线段中的最大数。 线段树的模板题，试用了一下交大的模板。效率有点略低。 代码： #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :
阅读更多...
hdu 1166 敌兵布阵（树状数组 or 线段树）

hdu 1166 敌兵布阵（树状数组 or 线段树）

题意是求一个线段的和，在线段上可以进行加减的修改。 树状数组的模板题。 代码： #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while
阅读更多...
hdu 3790 (单源最短路dijkstra）

hdu 3790 (单源最短路dijkstra）

题意： 每条边都有长度d 和花费p，给你起点s 终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。 解析： 考察对dijkstra的理解。 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstrin
阅读更多...
hdu 2489 (dfs枚举 + prim)

hdu 2489 (dfs枚举 + prim)

题意： 对于一棵顶点和边都有权值的树，使用下面的等式来计算Ratio 给定一个n 个顶点的完全图及它所有顶点和边的权值，找到一个该图含有m 个顶点的子图，并且让这个子图的Ratio 值在所有m 个顶点的树中最小。 解析： 因为数据量不大，先用dfs枚举搭配出m个子节点，算出点和，然后套个prim算出边和，每次比较大小即可。 dfs没有写好，A的老泪纵横。 错在把index在d
阅读更多...
hdu 1102 uva 10397（最小生成树prim）

hdu 1102 uva 10397（最小生成树prim）

hdu 1102: 题意： 给一个邻接矩阵，给一些村庄间已经修的路，问最小生成树。 解析： 把已经修的路的权值改为0，套个prim（）。 注意prim 最外层循坏为n-1。 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstri
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2