联盟营销网站有哪些,杭州公司网站建设,yw55523can优物入口4虎,学校网站建设项目背景Description 深绘里一直很讨厌雨天。灼热的天气穿透了前半个夏天#xff0c;后来一场大雨和随之而来的洪水#xff0c;浇灭了一切。虽然深绘里家乡的小村落对洪水有着顽固的抵抗力#xff0c;但也倒了几座老房子#xff0c;几棵老树被连根拔起#xff0c;以及田地里的粮食…Description 深绘里一直很讨厌雨天。 灼热的天气穿透了前半个夏天后来一场大雨和随之而来的洪水浇灭了一切。 虽然深绘里家乡的小村落对洪水有着顽固的抵抗力但也倒了几座老房子几棵老树被连 根拔起以及田地里的粮食被弄得一片狼藉。 无奈的深绘里和村民们只好等待救济粮来维生。 不过救济粮的发放方式很特别。 首先村落里的一共有n 座房屋并形成一个树状结构。然后救济粮分m 次发放每次选择 两个房屋(x,y)然后对于x 到y 的路径上含x 和y) 每座房子里发放一袋z 类型的救济粮。 然后深绘里想知道当所有的救济粮发放完毕后每座房子里存放的最多的是哪种救济粮。 Input 第一行两个正整数n,m含义如题目所示。 接下来n-1 行每行两个数(a,b)表示(a,b) 间有一条边。 再接下来m 行每行三个数(x,y,z)含义如题目所示。 Output n 行第i 行一个整数表示第i 座房屋里存放的最多的是哪种救济粮如果有多种救济粮 存放次数一样输出编号最小的。 如果某座房屋里没有救济粮则对应一行输出0。 Sample Input 5 3
1 2
3 1
3 4
5 4
2 3 3
1 5 2
3 3 3 Sample Output 2
3
3
2
2 Data Constraint 对于20% 的数据1 n,m 100 对于50% 的数据1 n,m 2000 对于100% 的数据1 n;m 100000; 1 a, b, x, y n; 1 z 10^9 题解 考虑如果是在一条链上的话要怎么做那么我们可以在x处加一个加入z的标记在y1出加入一个删掉z的标记然后用权值线段树扫一遍就好了现在拓展到一棵树上我们可以在x和y处加入一个加上z的标记在lca和fa[lca]处加入一个删除z的标记那么我们每次可以把子节点的线段树合并上来然后处理标记信息最后查询答案即可代码 1 #include cstdio2 #include iostream3 #include cstring4 #include vector5 #define N 1000106 using namespace std;7 struct tree { int l,r,sum,v; }t[N*50];8 int n,m,cnt,deep[N],a[N],root[N],fa[N][18],ans[N];9 vectorinte[N],p[N],q[N];
10 void pushup(int x) { if (t[t[x].r].sumt[t[x].l].sum) t[x].sumt[t[x].r].sum,t[x].vt[t[x].r].v; else t[x].sumt[t[x].l].sum,t[x].vt[t[x].l].v; }
11 void dfs(int x,int f,int dep)
12 {
13 fa[x][0]f,deep[x]dep,root[x]x,cnt;
14 for (int i1;i17;i) fa[x][i]fa[fa[x][i-1]][i-1];
15 for (int i0;ie[x].size();i) if (e[x][i]!f) dfs(e[x][i],x,dep1);
16 }
17 int LCA(int x,int y)
18 {
19 if (deep[x]deep[y]) swap(x,y);
20 for (int i17;i0;i--) if (deep[fa[x][i]]deep[y]) xfa[x][i];
21 if (xy) return x;
22 for (int i17;i0;i--) if (fa[x][i]!fa[y][i]) xfa[x][i],yfa[y][i];
23 return fa[x][0];
24 }
25 int update(int d,int l,int r,int x,int y)
26 {
27 if (!d) dcnt;
28 if (lr) { t[d].sumy,t[d].vl; return 0; }
29 int midlr1;
30 if (xmid) update(t[d].l,l,mid,x,y); else update(t[d].r,mid1,r,x,y);
31 pushup(d);
32 }
33 int merge(int x,int y,int l,int r)
34 {
35 if (!x) return y;
36 if (!y) return x;
37 if (lr) { t[x].sumt[y].sum,t[x].vl; return x; }
38 int midlr1;
39 t[x].lmerge(t[x].l,t[y].l,l,mid),t[x].rmerge(t[x].r,t[y].r,mid1,r);
40 pushup(x); return x;
41 }
42 void dfs1(int x,int pre)
43 {
44 for (int i0;ie[x].size();i) if (e[x][i]!pre) dfs1(e[x][i],x),merge(root[x],root[e[x][i]],1,N-10);
45 for (int i0;ip[x].size();i) update(root[x],1,N-10,p[x][i],1);
46 for (int i0;iq[x].size();i) update(root[x],1,N-10,q[x][i],-1);
47 ans[x]t[root[x]].v;
48 }
49 int main()
50 {
51 scanf(%d%d,n,m);
52 for (int i1,x,y;in;i) scanf(%d%d,x,y),e[x].push_back(y),e[y].push_back(x);
53 dfs(1,0,1);
54 for (int i1,x,y,z;im;i)
55 {
56 scanf(%d%d%d,x,y,z);
57 int lcaLCA(x,y);
58 p[x].push_back(z),p[y].push_back(z),q[lca].push_back(z);
59 if (fa[lca][0]) q[fa[lca][0]].push_back(z);
60 }
61 dfs1(1,0);
62 for (int i1;in;i) printf(%d\n,ans[i]);
63 } 转载于:https://www.cnblogs.com/Comfortable/p/11176223.html
