网站开发进度把握,wordpress自动跳转,Wordpress点金,云南省住房城乡建设厅网站题意#xff1a;一棵 nnn 个点的树#xff0c;每个点有两个权值 ai,bia_i,b_iai,bi#xff0c;有黑白两种颜色。mmm 次询问#xff0c;每次给定一个 kkk,求一条端点异色的路径#xff0c;使得 k∑ai∑bik\sum a_i\sum b_ik∑ai∑bi 最大化。 n≤2105n\leq 2\times…题意一棵 nnn 个点的树每个点有两个权值 ai,bia_i,b_iai,bi有黑白两种颜色。mmm 次询问每次给定一个 kkk,求一条端点异色的路径使得 k∑ai∑bik\sum a_i\sum b_ik∑ai∑bi 最大化。
n≤2×105n\leq 2\times 10^5n≤2×105
就差把“请在边分治的时候维护闵可夫斯基和”写题面上了……
直观来看是把 (ai,bi)(a_i,b_i)(ai,bi) 看成直线但是并不好维护。不过半平面交和凸包是对偶的并且凸包合并有闵可夫斯基和这个东西所以可以把每个结点直接看成点维护凸包询问的时候二分就可以了。
分治的时候对两边黑白分别求出凸壳然后交叉合并把点丢到答案集合里最后再做一个凸包就可以了。
然后就是三度化后处理答案的问题。把新建的虚点的参数从父亲那里复制然后如果路径的 lca 是虚点强行给它加上去。可以在 dfs 的时候记一个当前走的方向然后如果是往上走的可以进行一次换方向并在这里统计当前点是否需要有贡献。
复杂度 O(nlogn)\Omicron(n\log n)O(nlogn)
#include iostream
#include cstdio
#include cstring
#include cctype
#include vector
#include algorithm
#define MAXN 200005
#define MAXM 400005
using namespace std;
const int INF0x7fffffff;
inline int read()
{int ans0,f1;char cgetchar();while (!isdigit(c)) (c-)(f-1),cgetchar();while (isdigit(c)) ans(ans3)(ans1)(c^48),cgetchar();return f*ans;
}
typedef long long ll;
struct point{int x,y;inline point(const int x0,const int y0):x(x),y(y){}};
inline point operator (const point a,const point b){return point(a.xb.x,a.yb.y);}
inline point operator -(const point a,const point b){return point(a.x-b.x,a.y-b.y);}
inline ll operator *(const point a,const point b){return (ll)a.x*b.y-(ll)a.y*b.x;}
inline bool operator (const point a,const point b){return a.xb.x||(a.xb.xa.yb.y);}
typedef vectorpoint hull;
#define s(t) ((int)(t).size())
void make_hull(hull A)
{hull t;sort(A.begin(),A.end());for (int i0;i(int)A.size();i){if (iA[i].xA[i-1].x) continue;while (s(t)1(t[s(t)-1]-t[s(t)-2])*(A[i]-t[s(t)-1])0) t.pop_back();t.push_back(A[i]);}At;
}
void merge(const hull A,const hull B,hull C)
{if (A.empty()||B.empty()) return;int i,j;hull ans;for (ij0;is(A)-1js(B)-1;){if ((A[i1]-A[i])*(B[j1]-B[j])0) ans.push_back(B[j1]-B[j]),j;else ans.push_back(A[i1]-A[i]),i;}while (is(A)-1) ans.push_back(A[i1]-A[i]),i;while (js(B)-1) ans.push_back(B[j1]-B[j]),j;point lasA[0]B[0];C.push_back(las);for (int i0;is(ans);i) C.push_back(laslasans[i]);
}
vectorint E[MAXN];
struct edge{int u,v;}e[MAXM];
int head[MAXN],nxt[MAXM],cnt1;
inline void addnode(int u,int v)
{e[cnt](edge){u,v};nxt[cnt]head[u];head[u]cnt;
}
point val[MAXN];
int vis[MAXN],dep[MAXN],type[MAXN],n,tot;
void dfs(int u)
{vis[u]1;if ((int)E[u].size()3){for (int i0;i(int)E[u].size();i)if (!vis[E[u][i]])dep[E[u][i]]dep[u]1,dfs(E[u][i]),addnode(u,E[u][i]),addnode(E[u][i],u); return; }int cur[2]{tot,tot},pos0;addnode(u,cur[0]),addnode(cur[0],u);addnode(u,cur[1]),addnode(cur[1],u);val[cur[0]]val[cur[1]]val[u];type[cur[0]]type[cur[1]]type[u];dep[cur[0]]dep[cur[1]]dep[u]1;for (int i0;i(int)E[u].size();i)if (!vis[E[u][i]])E[cur[pos^1]].push_back(E[u][i]);dfs(cur[0]),dfs(cur[1]);
}
int tp;
int rt,mn,siz[MAXN];
void findrt(int u,int f,int sum)
{siz[u]1;for (int ihead[u];i;inxt[i])if (!vis[i1]e[i].v!f){findrt(e[i].v,u,sum);if (max(siz[e[i].v],sum-siz[e[i].v])mn) mnmax(siz[e[i].v],sum-siz[e[i].v]),rti;siz[u]siz[e[i].v];}
}
hull A[2],B[2],lis;
void dfs(int u,int f,point cur,hull* A,bool up)
{if (un) A[type[u]].push_back(curcurval[u]);for (int ihead[u];i;inxt[i])if (!vis[i1]e[i].v!f(up^(dep[e[i].v]dep[u])))dfs(e[i].v,u,cur,A,up);if (up){if (un) A[type[u]].push_back(curcurval[u]);for (int ihead[u];i;inxt[i])if (!vis[i1]e[i].v!fdep[e[i].v]dep[u])dfs(e[i].v,u,cur,A,0);}
}
void calc()
{A[0].clear(),A[1].clear();B[0].clear(),B[1].clear();int ue[rt].u,ve[rt].v;if (dep[u]dep[v]) swap(u,v);dfs(v,0,point(0,0),A,0);dfs(u,0,point(0,0),B,1);make_hull(A[0]),make_hull(A[1]);make_hull(B[0]),make_hull(B[1]);merge(A[0],B[1],lis);merge(A[1],B[0],lis);
}
void solve(int sum)
{if (mnINF) return;vis[rt1]1;calc();int currt,szsiz[e[rt].v];mnINF,findrt(e[cur].v,0,sz),solve(sz);mnINF,findrt(e[cur].u,0,sum-sz),solve(sum-sz);
}
int main()
{totnread();int mread();for (int i1;in;i) val[i].xread();for (int i1;in;i) val[i].yread();for (int i1;in;i) type[i]read();for (int i1;in;i){int u,v;uread(),vread();E[u].push_back(v),E[v].push_back(u);}dep[1]1,dfs(1);memset(vis,0,sizeof(vis));mnINF,findrt(1,0,tot),solve(tot);make_hull(lis);
// for (int i0;i(int)lis.size();i) printf(%d %d\n,lis[i].x,lis[i].y);lis.push_back(point(lis.back().x,-INF));while (m--){int kread();int l0,rs(lis)-2,mid;while (lr){mid(lr)1;if (point(1,-k)*(lis[mid1]-lis[mid])0) lmid1;else rmid;}printf(%lld\n,(ll)k*lis[l].xlis[l].y);}return 0;
}
