P3313 [SDOI2014] 旅行（分块做法）

本文主要是介绍P3313 [SDOI2014] 旅行（分块做法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

P3313 [SDOI2014] 旅行总题单链接

思路

遇到这种树上路径问题，就考虑用重链剖分转为区间问题。

问题转换为了：给定一个区间和 $k$ ，求这个区间内信仰为 $k$ 的城市的权值和或最大权值。

这个问题也可以用动态开点线段树解决（现在不会，以后再讲），但今天的主角是分块。

查询就是一般的分块查询。而修改，因为要求最大值，所以直接 $O(\sqrt{n})$ 暴力修改即可。

代码

#include<bits/stdc++.h>
#define ll long long
#define fir first
#define sec second
#define endl '\n'
using namespace std;vector<ll>eg[100005];
pair<ll,ll>cpo[100005];ll n,Q,id[100005],di[100005];class CLK{public:ll B,pos[100005];struct BLK{ll L,R,sm[100005],mx[100005];}blk[350];void init(){B=sqrt(n);for(ll i=1;i<=B;i++){blk[i].L=(i-1)*B+1,blk[i].R=i*B;for(ll j=blk[i].L;j<=blk[i].R;j++){pos[j]=i;blk[i].sm[cpo[di[j]].sec]+=cpo[di[j]].fir;blk[i].mx[cpo[di[j]].sec]=max(blk[i].mx[cpo[di[j]].sec],cpo[di[j]].fir);}}if(blk[B].R<n){B++;blk[B].L=blk[B-1].R+1;blk[B].R=n;for(ll j=blk[B].L;j<=blk[B].R;j++){pos[j]=B;blk[B].sm[cpo[di[j]].sec]+=cpo[di[j]].fir;blk[B].mx[cpo[di[j]].sec]=max(blk[B].mx[cpo[di[j]].sec],cpo[di[j]].fir);}}}inline void clear(ll p){for(ll j=blk[p].L;j<=blk[p].R;j++){blk[p].sm[cpo[di[j]].sec]=0;blk[p].mx[cpo[di[j]].sec]=0;}}inline void adsmx(ll p){for(ll j=blk[p].L;j<=blk[p].R;j++){blk[p].sm[cpo[di[j]].sec]+=cpo[di[j]].fir;blk[p].mx[cpo[di[j]].sec]=max(blk[p].mx[cpo[di[j]].sec],cpo[di[j]].fir);}}inline void modify_1(ll p,ll k){clear(pos[id[p]]);cpo[p].fir=k;adsmx(pos[id[p]]);}inline void modify_2(ll p,ll k){clear(pos[id[p]]);cpo[p].sec=k;adsmx(pos[id[p]]);}inline ll query_1(ll x,ll y,ll k){ll res=0;if(pos[x]==pos[y]){for(ll i=x;i<=y;i++)if(cpo[di[i]].sec==k)res+=cpo[di[i]].fir;return res;}for(ll i=x;i<=blk[pos[x]].R;i++)if(cpo[di[i]].sec==k)res+=cpo[di[i]].fir;for(ll i=y;i>=blk[pos[y]].L;i--)if(cpo[di[i]].sec==k)res+=cpo[di[i]].fir;for(ll i=pos[x]+1;i<pos[y];i++)res+=blk[i].sm[k];return res;}inline ll query_2(ll x,ll y,ll k){ll res=0;if(pos[x]==pos[y]){for(ll i=x;i<=y;i++)if(cpo[di[i]].sec==k)res=max(res,cpo[di[i]].fir);return res;}for(ll i=x;i<=blk[pos[x]].R;i++)if(cpo[di[i]].sec==k)res=max(res,cpo[di[i]].fir);for(ll i=y;i>=blk[pos[y]].L;i--)if(cpo[di[i]].sec==k)res=max(res,cpo[di[i]].fir);for(ll i=pos[x]+1;i<pos[y];i++)res=max(res,blk[i].mx[k]);return res;}}clk;class TRE{public:ll dep[100005],siz[100005],tot;ll son[100005],fas[100005],top[100005];void dfs_1(ll fa,ll p){dep[p]=dep[fa]+1;siz[p]=1;fas[p]=fa;for(ll v:eg[p]){if(v==fa)continue;dfs_1(p,v);siz[p]+=siz[v];if(siz[son[p]]<siz[v])son[p]=v;}}void dfs_2(ll p,ll tpo){id[p]=++tot;di[tot]=p;top[p]=tpo;if(son[p])dfs_2(son[p],tpo);for(ll v:eg[p]){if(v==fas[p]||v==son[p])continue;dfs_2(v,v);}}void init(){dfs_1(0,1);dfs_2(1,1);clk.init();}inline ll query_1(ll x,ll y,ll k){ll res=0;while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]])swap(x,y);res+=clk.query_1(id[top[x]],id[x],k);x=fas[top[x]];}if(dep[x]>dep[y])swap(x,y);res+=clk.query_1(id[x],id[y],k);return res;}inline ll query_2(ll x,ll y,ll k){ll res=0;while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]])swap(x,y);res=max(res,clk.query_2(id[top[x]],id[x],k));x=fas[top[x]];}if(dep[x]>dep[y])swap(x,y);res=max(res,clk.query_2(id[x],id[y],k));return res;}}tre;signed main(){ios::sync_with_stdio(false);cin>>n>>Q;for(ll i=1;i<=n;i++)cin>>cpo[i].fir>>cpo[i].sec;for(ll i=1;i<n;i++){ll x,y;cin>>x>>y;eg[x].push_back(y);eg[y].push_back(x);}tre.init();while(Q--){char op;ll x,y;cin>>op>>op>>x>>y;if(op=='C')clk.modify_2(x,y);if(op=='W')clk.modify_1(x,y);if(op=='S')cout<<tre.query_1(x,y,cpo[x].sec)<<endl;if(op=='M')cout<<tre.query_2(x,y,cpo[x].sec)<<endl;}return 0;
}