description

深繪里一直很討厭雨天。

灼熱的天氣穿透了前半個夏天，后來一場大雨和隨之而來的洪水，澆滅了一切。

雖然深繪里家鄉(xiāng)的小村落對洪水有著頑固的抵抗力，但也倒了幾座老房子，幾棵老樹被連

根拔起，以及田地里的糧食被弄得一片狼藉。

無奈的深繪里和村民們只好等待救濟糧來維生。

不過救濟糧的發(fā)放方式很特別。

首先村落里的一共有n 座房屋，并形成一個樹狀結(jié)構(gòu)。然后救濟糧分m 次發(fā)放，每次選擇

兩個房屋(x,y)，然后對于x 到y(tǒng) 的路徑上（含x 和y) 每座房子里發(fā)放一袋z 類型的救濟糧。

然后深繪里想知道，當(dāng)所有的救濟糧發(fā)放完畢后，每座房子里存放的最多的是哪種救濟糧。

---

analysis

• 樹上倍增\(+\)樹上差分\(+\)線段樹合并

• 可以在\(x,y\)打上\(1\)標(biāo)記，\(LCA,fa[LCA]\)打上\(-1\)標(biāo)記

• 這樣合并子樹信息時到\(LCA\)剛好只算一次，到\(fa[LCA]\)就沒算

• 找\(LCA\)當(dāng)然可以用倍增

• 線段樹合并大概就是把兩棵線段樹維護(hù)同一區(qū)間的節(jié)點的左右兒子信息合并一下

• 如果一邊沒有某個兒子就把另一個節(jié)點的那個兒子接上，復(fù)雜度是\(O(\log_2n)\)的

• 由于節(jié)點非常多所以動態(tài)開點，所有操作后從葉子節(jié)點到根一層層合并線段樹就好

• 感覺這題知識點很多，不能偷懶，要好好學(xué)…

---

code

#pragma GCC optimize("O3") #pragma G++ optimize("O3") #include<stdio.h> #include<string.h> #include<algorithm> #define MAX 200000 #define MAXN 200005 #define MAXM 6000005 #define ll long long #define reg register ll #define fo(i,a,b) for (reg i=a;i<=b;++i) #define fd(i,a,b) for (reg i=a;i>=b;--i) #define rep(i,a) for (reg i=last[a];i;i=next[i])using namespace std;ll last[MAXN<<1],next[MAXN<<1],tov[MAXN<<1]; ll depth[MAXN],ans[MAXN],root[MAXN]; ll anc[MAXN][19],lson[MAXM],rson[MAXM]; ll n,m,tot; pair<ll,ll>tr[MAXM];struct node {ll x,y,z; }f[MAXN];inline ll read() {ll x=0,f=1;char ch=getchar();while (ch<'0' || '9'<ch){if (ch=='-')f=-1;ch=getchar();}while ('0'<=ch && ch<='9')x=x*10+ch-'0',ch=getchar();return x*f; } inline ll max(ll x,ll y){return x>y?x:y;} inline void swap(ll &x,ll &y){ll z=x;x=y,y=z;} inline void link(ll x,ll y){next[++tot]=last[x],last[x]=tot,tov[tot]=y;} inline void dfs(ll x){rep(i,x)if (tov[i]!=anc[x][0])depth[tov[i]]=depth[x]+1,anc[tov[i]][0]=x,dfs(tov[i]);} inline ll lca(ll x,ll y) {if (depth[x]<depth[y])swap(x,y);fd(i,18,0)if (depth[anc[x][i]]>=depth[y])x=anc[x][i];if (x==y)return x;fd(i,18,0)if (anc[x][i]!=anc[y][i])x=anc[x][i],y=anc[y][i];return anc[x][0]; } inline void insert(ll &t,ll l,ll r,ll x,ll y) {if (!t)t=++tot;if (l==r){tr[t]=make_pair(tr[t].first+y,-x);return;}ll mid=(l+r)>>1;if (x<=mid)insert(lson[t],l,mid,x,y);else insert(rson[t],mid+1,r,x,y);tr[t]=max(tr[lson[t]],tr[rson[t]]); } inline ll merge(ll x,ll y,ll l,ll r) {if (!x)return y;if (!y)return x;ll mid=(l+r)>>1;if (l==r){tr[x].first+=tr[y].first;return x;}lson[x]=merge(lson[x],lson[y],l,mid),rson[x]=merge(rson[x],rson[y],mid+1,r),tr[x]=max(tr[lson[x]],tr[rson[x]]);return x; } inline void dfs_merge(ll x) {rep(i,x)if (tov[i]!=anc[x][0])dfs_merge(tov[i]),root[x]=merge(root[x],root[tov[i]],1,MAX);ans[x]=-tr[root[x]].second; } int main() {freopen("T3.in","r",stdin);n=read(),m=read();fo(i,1,n-1){ll x=read(),y=read();link(x,y),link(y,x);}depth[1]=1,dfs(1),tot=0;fo(j,1,18)fo(i,1,n)anc[i][j]=anc[anc[i][j-1]][j-1];while (m--){ll x=read(),y=read(),z=read(),tmp=lca(x,y);insert(root[x],1,MAX,z,1),insert(root[y],1,MAX,z,1),insert(root[tmp],1,MAX,z,-1),insert(root[anc[tmp][0]],1,MAX,z,-1);}dfs_merge(1);fo(i,1,n)printf("%lld\n",ans[i]);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/horizonwd/p/11178589.html

總結(jié)

以上是生活随笔為你收集整理的【JZOJ3397】【luoguP4556】雨天的尾巴的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。