首页 > 代码库 > GDOI模拟雨天的尾巴【树套树】
GDOI模拟雨天的尾巴【树套树】
雨天的尾巴
深绘里一直很讨厌雨天。
灼热的天气穿透了前半个夏天，后来一场大雨和随之而来的洪水，浇灭了一切。
虽然深绘里家乡的小村落对洪水有着顽固的抵抗力，但也倒了几座老房子，几棵老树被连根拔起，以及田地里的粮食被弄得一片狼藉。
无奈的深绘里和村民们只好等待救济粮来维生。
不过救济粮的发放方式很特别。
首先村落里的一共有n 座房屋，并形成一个树状结构。然后救济粮分m 次发放，每次选择两个房屋(x,y)，然后对于x 到y 的路径上（含x 和y) 每座房子里发放一袋z 类型的救济粮。
然后深绘里想知道，当所有的救济粮发放完毕后，每座房子里存放的最多的是哪种救济粮。
输入格式：
第一行两个正整数n,m，含义如题目所示。接下来n-1 行，每行两个数(a,b)，表示(a,b) 间有一条边。
再接下来m 行，每行三个数(x,y,z)，含义如题目所示。
输出格式：
n 行，第i 行一个整数，表示第i 座房屋里存放的最多的是哪种救济粮，如果有多种救济粮存放次数一样，输出编号最小的。
如果某座房屋里没有救济粮，则对应一行输出0。
样例输入：
5 3 1 2 3 1 3 4 5 4 2 3 3 1 5 2 3 3 3
样例输出：
2 3 3 0 2
数据范围：
对于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到y的路径上放置z粮食，可在lca(x,y)与F[lca(x,y)]将z-1，x与y上z+1.
还有一个东西叫线段树合并，这样可以把儿子处理完后全部合并到父亲上，x与y的lca刚好合加过两次，所以lca的线段树z-1，lca的父节点z-1，也就是合并到了时z就减到0了.
lca用ST求好了.
1 #include<cstdio>
2 #include<iostream>
3 using namespace std;
4 const int N=100005;
5 const int M=20000005;
6 int Head[N],Next[N*2],V[N*2],cnt=0;//store the tree structure before DFS
7 int Ans[N],ST[N][17],dep[N],F[N];//store the DP data for ST to get LCA
8 int lch[M],rch[M],size,key[M];//store the inner tree----key[] records the maximum of the food.same.count()
9 int Hash[N],n;//z can be as big as 10^9 so hash can condense it to an acceptable range
10 inline void Link(int x,int y)
11 {
12 cnt++;
13 V[cnt]=y;
14 Next[cnt]=Head[x];
15 Head[x]=cnt;
16 }
17 inline void Dfs(int x,int f,int D)
18 {
19 dep[x]=D;
20 F[x]=f;
21 ST[x][0]=f;
22 for(int i=1;i<=16;i++)
23 {
24 if(dep[x]-(1<<i)>=1) ST[x][i]=ST[ST[x][i-1]][i-1];
25 else break;
26 }
27 for(int i=Head[x];i;i=Next[i]) if(V[i]!=f) Dfs(V[i],x,D+1);
28 }
29 inline int LCA(int x,int y)
30 {
31 if(dep[x]>dep[y])
32 {
33 for(int i=16;i>=0;i--) if(dep[ST[x][i]]>=dep[y]) x=ST[x][i];
34 }
35 else if(dep[y]>dep[x])
36 {
37 for(int i=16;i>=0;i--) if(dep[ST[y][i]]>=dep[x]) y=ST[y][i];
38 }//move x and y to the same depth
39 if(x==y) return x;
40 for(int i=16;i>=0;i--)
41 {
42 if(ST[y][i]!=ST[x][i])
43 {
44 y=ST[y][i];
45 x=ST[x][i];
46 }
47 }
48 return F[x];
49 }
50 inline int Find_Space(int x)
51 {
52 int p=x%N;
53 while(Hash[p]!=x&&Hash[p]!=0)
54 {
55 p++;
56 if(p==N) p=0;
57 }
58 if(!Hash[p]) Hash[p]=x;
59 return p;
60 }
61 inline void Insert(int &x,int l,int r,int num,int k)
62 {
63 if(x==0) x=++size;
64 if(l==r)
65 {
66 key[x]+=k;
67 return;
68 }
69 int mid=(l+r)>>1;
70 if(num<=mid) Insert(lch[x],l,mid,num,k);
71 else Insert(rch[x],mid+1,r,num,k);
72 key[x]=max(key[lch[x]],key[rch[x]]);
73 }
74 inline void Merge(int p,int fp,int l,int r)
75 {
76 if(l==r)
77 {
78 key[fp]+=key[p];
79 return;
80 }
81 int mid=(l+r)>>1;
82 if(lch[p])
83 {
84 if(!lch[fp]) lch[fp]=lch[p];
85 else Merge(lch[p],lch[fp],l,mid);
86 }
87 if(rch[p])
88 {
89 if(!rch[fp]) rch[fp]=rch[p];
90 else Merge(rch[p],rch[fp],mid+1,r);
91 }
92 key[fp]=max(key[lch[fp]],key[rch[fp]]);
93 }
94 inline int Query(int p,int l,int r)
95 {
96 if(!p) return 0;
97 if(l==r) return l;
98 int mid=(l+r)>>1;
99 if(key[lch[p]]>=key[rch[p]])
100 {
101 if(key[lch[p]]>0) return Query(lch[p],l,mid);
102 else return 0;
103 }
104 else
105 {
106 if(key[rch[p]]>0) return Query(rch[p],mid+1,r);
107 else return 0;
108 }
109 }
110 inline void Reply(int x)
111 {
112 for(int i=Head[x];i;i=Next[i]) if(V[i]!=F[x])
113 {
114 Reply(V[i]);
115 Merge(V[i],x,1,N);//merge the zone tree to its outer father‘s zone tree
116 }
117 Ans[x]=Query(x,1,N);
118 }
119 int main()
120 {
121 int m,x,y,z,anc;
122 scanf("%d%d",&n,&m);
123 size=n*2;
124 for(int i=1;i<n;i++)
125 {
126 scanf("%d%d",&x,&y);
127 Link(x,y);
128 Link(y,x);
129 }
130 Dfs(1,0,1);
131 while(m--)
132 {
133 scanf("%d%d%d",&x,&y,&z);
134 z=Find_Space(z);
135 anc=LCA(x,y);
136 Insert(x,1,N,z,1);
137 Insert(y,1,N,z,1);
138 Insert(anc,1,N,z,-1);
139 if(F[anc]) Insert(F[anc],1,N,z,-1);
140 }
141 Reply(1);
142 for(int i=1;i<=n;i++) printf("%d\n",Hash[Ans[i]]);
143 return 0;
144 }
GDOI模拟雨天的尾巴【树套树】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。