缔客网络上海响应式网站建设,wordpress 备份云盘,wordpress落叶插件,网站开发技术笔记正题
题目链接:https://www.luogu.com.cn/problem/P3345 题目大意 nnn个点的一棵树#xff0c;每次修改一个点的点权后询问一个xxx最小化∑y1ndis(x,y)∗dy\sum_{y1}^ndis(x,y)*d_yy1∑ndis(x,y)∗dy 解题思路
先是构建一个点分树#xff0c;然后考虑如何计算答案。
我…正题
题目链接:https://www.luogu.com.cn/problem/P3345 题目大意
nnn个点的一棵树每次修改一个点的点权后询问一个xxx最小化∑y1ndis(x,y)∗dy\sum_{y1}^ndis(x,y)*d_yy1∑ndis(x,y)∗dy 解题思路
先是构建一个点分树然后考虑如何计算答案。
我们定义一个frxfr_xfrx表示点分树上faxfa_xfax到xxx所在子树的路径上第一个节点我们可以比较frxfr_xfrx的答案和faxfa_xfax的答案如果frxfr_xfrx更大那么就向xxx移动。那么如何计算两个节点的答案的我们需要维护三个值sdx,sxx,sfxsd_x,sx_x,sf_xsdx,sxx,sfx分别表示下面的子树都是点分子树xxx子树内的点权和xxx子树内的∑y1ndis(x,y)∗dy\sum_{y1}^ndis(x,y)*d_y∑y1ndis(x,y)∗dyxxx子树内的所有点∑y1ndis(fax,y)∗dy\sum_{y1}^ndis(fa_x,y)*d_y∑y1ndis(fax,y)∗dy。
这样我们就可以通过枚举到根节点的路径计算每个点的答案时间复杂度O(nlog3n)O(n\log^3 n)O(nlog3n)因为有LCALCALCA求路径长度。
考虑优化我们可以用RMQRMQRMQ求LCALCALCA每次到一个点时序列中加入这个点然后回退时加入父节点之后询问一个区间中深度最小的节点即可。
时间复杂度O(nlog2n)O(n\log^2 n)O(nlog2n) codecodecode
#includecstdio
#includecstring
#includealgorithm
#includevector
#includestack
#define mp(x,y) make_pair(x,y)
#define ll long long
using namespace std;
const int N2e510,T22;
struct node{int to,next,w;
}a[N*2];
int n,m,tot,cnt,ls[N],dep[N],dis[N],f[N][T],lg[N],dfn[N],rfn[N];
int num,root,f0[N],siz[N],fa[N],sd[N],fr[N];ll sw[N],sx[N];
bool v[N];vectorint e[N];stackint s;
//struct heap{
// priority_queuepairint,int q1,q2;
// void push(pairint,int x)
// {q1.push(x);return;}
// void pop(pairint,int x)
// {q2.push(x);return;}
// pairint,int top(){
// while(!q2.empty()q1.top()q2.top())
// q1.pop(),q2.pop();
// return q1.top();
// }
// int size(){return q1.size()-q2.size();}
//}q[N];
void addl(int x,int y,int w){a[tot].toy;a[tot].nextls[x];ls[x]tot;a[tot].ww;return;
}
void dfs(int x,int fa){dfn[cnt]x;rfn[x]cnt;dep[x]dep[fa]1;for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa)continue;dis[y]dis[x]a[i].w;dfs(y,x);dfn[cnt]x;}return;
}
void init(){dfs(1,1);for(int i1;icnt;i)f[i][0]dfn[i];for(int i2;icnt;i)lg[i]lg[i/2]1;for(int j1;(1j)cnt;j)for(int i1;i(1j)-1cnt;i){int xf[i][j-1],yf[i(1j-1)][j-1];f[i][j]dep[x]dep[y]?x:y;}return;
}
int LCA(int x,int y){int lrfn[x],rrfn[y];if(lr)swap(l,r);int zlg[r-l1];xf[l][z];yf[r-(1z)1][z];return dep[x]dep[y]?x:y;
}
int get_dis(int x,int y)
{return dis[x]dis[y]-2*dis[LCA(x,y)];}
void groot(int x,int fa){siz[x]1;f0[x]0;for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa||v[y])continue;groot(y,x);siz[x]siz[y];f0[x]max(f0[x],siz[y]);}f0[x]max(f0[x],num-siz[x]);if(f0[x]f0[root])rootx;return;
}
void build(int x){v[x]1;int Snum;for(int ils[x];i;ia[i].next){int ya[i].to;if(v[y])continue;num(siz[y]siz[x])?(S-siz[x]):(siz[y]);root0;groot(y,x);fr[root]y;yroot;build(y);fa[y]x;e[x].push_back(y);}return;
}
ll count(int x){ll anssx[x];for(int yx;fa[y];yfa[y])ans1ll*(sd[fa[y]]-sd[y])*get_dis(x,fa[y])sx[fa[y]]-sw[y];return ans;
}
int main()
{freopen(tree1.in,r,stdin);scanf(%d%d,n,m);for(int i1;in;i){int x,y,w;scanf(%d%d%d,x,y,w);addl(x,y,w);addl(y,x,w);}init();numn;f0[0]n;groot(1,1);int prroot;build(root);while(m--){int x,w,y;scanf(%d%d,x,w);yx;while(x){ll z1ll*w*get_dis(y,fa[x]?fa[x]:x);sw[x]z;sx[fa[x]]z;sd[x]w;xfa[x];}xpr;ll anscount(x);while(1){if(e[x].empty())break;ll z0;bool flag0;anscount(x);for(int i0;ie[x].size();i)if((zcount(fr[e[x][i]]))ans){xe[x][i];flag1;break;}if(flag)continue;break;}anscount(x);printf(%lld\n,ans);}return 0;
}
