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的標記，在y+1出加入一個刪掉z的標記，然后用權值線段樹掃一遍就好了
• 現在拓展到一棵樹上，我們可以在x和y處加入一個加上z的標記，在lca和fa[lca]處加入一個刪除z的標記，那么我們每次可以把子節點的線段樹合并上來
• 然后處理標記信息，最后查詢答案即可

代碼

1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 #include <vector> 5 #define N 100010 6 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 vector<int>e[N],p[N],q[N]; 10 void pushup(int x) { if (t[t[x].r].sum>t[t[x].l].sum) t[x].sum=t[t[x].r].sum,t[x].v=t[t[x].r].v; else t[x].sum=t[t[x].l].sum,t[x].v=t[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 i=1;i<=17;i++) fa[x][i]=fa[fa[x][i-1]][i-1]; 15 for (int i=0;i<e[x].size();i++) if (e[x][i]!=f) dfs(e[x][i],x,dep+1); 16 } 17 int LCA(int x,int y) 18 { 19 if (deep[x]<deep[y]) swap(x,y); 20 for (int i=17;i>=0;i--) if (deep[fa[x][i]]>=deep[y]) x=fa[x][i]; 21 if (x==y) return x; 22 for (int i=17;i>=0;i--) if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[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) d=++cnt; 28 if (l==r) { t[d].sum+=y,t[d].v=l; return 0; } 29 int mid=l+r>>1; 30 if (x<=mid) update(t[d].l,l,mid,x,y); else update(t[d].r,mid+1,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 (l==r) { t[x].sum+=t[y].sum,t[x].v=l; return x; } 38 int mid=l+r>>1; 39 t[x].l=merge(t[x].l,t[y].l,l,mid),t[x].r=merge(t[x].r,t[y].r,mid+1,r); 40 pushup(x); return x; 41 } 42 void dfs1(int x,int pre) 43 { 44 for (int i=0;i<e[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 i=0;i<p[x].size();i++) update(root[x],1,N-10,p[x][i],1); 46 for (int i=0;i<q[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 i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),e[x].push_back(y),e[y].push_back(x); 53 dfs(1,0,1); 54 for (int i=1,x,y,z;i<=m;i++) 55 { 56 scanf("%d%d%d",&x,&y,&z); 57 int lca=LCA(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 i=1;i<=n;i++) printf("%d\n",ans[i]); 63 }

?

轉載于:https://www.cnblogs.com/Comfortable/p/11176223.html

總結

以上是生活随笔為你收集整理的[线段树][树上差分] Jzoj P3397 雨天的尾巴的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。