怎么建立公司网站,知识库主题 wordpress,推销产品的软文500字,宿迁哪里做网站题目大意#xff1a; 有边权点权的树#xff0c;动态修改点权 每次修改后求带权重心x (\(minimize\) \(S\sum_i val[i]*dist[x][i]\)) 分析#xff1a; 从暴力找突破口#xff1a; 对于边x,y#xff0c;设长度为len#xff0c;切断后x半边树权值和为\(w_1\)#xff0c;y…题目大意 有边权点权的树动态修改点权 每次修改后求带权重心x (\(minimize\) \(S\sum_i val[i]*dist[x][i]\)) 分析 从暴力找突破口 对于边x,y设长度为len切断后x半边树权值和为\(w_1\)y半边树为\(w_2\) 若从重心从x转到到y,则\(Sw_1*len-w_2*len\) y比x优当且仅当\(w_2w_1\) 设当前根为root若root的一儿子x满足\(w_xw_{root}-w_x\)则x更优且可以证明\(w_x\frac {w_{root}} 2\),即不会存在第二个儿子y也比root优 做法 暴力做法深度无保证但\(w_xw_{root}-w_x\)可以确定答案在x子树 我们用点分治树保证深度 新的问题点分治树怎么求w 对于边x,y,设x半边树中所有点到x距离为\(d_1\),y半边树中所有点到y距离为\(d_2\) 所有点到x距离为\(d_1d_2w_2*len\) 所有点到y距离为\(d_1d_2w_1*len\) 可以了啊这就是动态点分治模板了 询问复杂度\(nlog^2n\) 后来信息队一位善于创新的大神想到了nlogn的方法 x为rty为点分儿子时 x在上则两边权值和分别为w(y)和w(root)-w(y) y在上则两边权值和分别为w(root)-w(x)w(y)和w(x)-w(y)乍一看非常正确用rmq求个lca就可以O(1)判上下超简便维护但如果如图 : 兜来兜去的图发现bug多多吸取经验 #include cstdio
#include cstdlib
#include cstring
#include algorithm
#include cmath
#include cctype
using namespace std;
typedef long long LL;
const int M100007;
const int NM*20*2;
inline int rd(){int x0;bool f1;char cgetchar();for(;!isdigit(c);cgetchar())if(c-)f0;for(;isdigit(c);cgetchar())xx*10c-48;return f?x:-x;
}int n,m;int g[M],te;
struct edge{int y,next;LL d;
}e[M1];
void addedge(int x,int y,LL d){e[te].yy;e[te].dd;e[te].nextg[x];g[x]te;
}int fir[M],td;
struct down{int y;//点分儿子int son;//亲儿子int next;
}dw[M];
void adddw(int x,int y,int son){dw[td].yy;dw[td].sonson;dw[td].nextfir[x];fir[x]td;
}int hd[M],tu;
struct uppp{int all,sub,next;LL dis;
}up[N];
void addup(int x,int all,int sub,LL dis){up[tu].allall;up[tu].subsub;up[tu].disdis;up[tu].nexthd[x];hd[x]tu;
}struct node{LL sum,val;
}a[M1];
int idrt,idsub,nw;int sz[M],vis[M];
int mi,size,rt,root;void getsz(int x,int fa){sz[x]1;int p,y;for(pg[x];p;pe[p].next)if(!vis[ye[p].y]y!fa){getsz(y,x);sz[x]sz[y];}
}void getrt(int x,int fa){int f,p,y;fsize-sz[x];for(pg[x];p;pe[p].next)if(!vis[ye[p].y]y!fa){getrt(y,x);fmax(f,sz[y]);}if(fmi) mif,rtx;
}void dfs(int x,int fa,LL dis){addup(x,idrt,idsub,dis);int p,y;for(pg[x];p;pe[p].next)if(!vis[ye[p].y]y!fa){dfs(y,x,dise[p].d);}
}void work(int frm,int drt){getsz(frm,0);misizesz[frm];getrt(frm,0);int xrt,p,y;vis[x]1;idrtnw;addup(x,idrt,-1,0);if(drt) adddw(drt,x,frm);else rootx;for(pg[x];p;pe[p].next)if(!vis[ye[p].y]){idsubnw;dfs(y,x,e[p].d);}for(pg[x];p;pe[p].next)if(!vis[ye[p].y]) work(y,x);
}void update(int x,LL y){int p;for(phd[x];p;pup[p].next){a[up[p].all].valy;a[up[p].all].sumy*up[p].dis;if(up[p].sub!-1){a[up[p].sub].valy;a[up[p].sub].sumy*up[p].dis;}}
}LL get(int x){LL res0;int p;for(phd[x];p;pup[p].next){resa[up[p].all].sum;resa[up[p].all].val*up[p].dis;if(up[p].sub!-1){res-a[up[p].sub].sum;res-a[up[p].sub].val*up[p].dis;}}return res;
}int anst;
void find(int x){int p,y,bb1;for(pfir[x];p;pdw[p].next)if(get(x)get(dw[p].son)){bb0;find(dw[p].y);break;}if(bb) anstx;
}int main(){int i,x,y,z;nrd();mrd();for(i1;in;i){xrd(),yrd(),zrd();addedge(x,y,z);addedge(y,x,z);}work(1,0);for(i1;im;i){xrd(),yrd();update(x,y);find(root);printf(%lld\n,get(anst));}return 0;
} 转载于:https://www.cnblogs.com/acha/p/6283355.html
