「JOISC 2019 Day3」指定城市 Solution
「JOISC 2019 Day3」指定城市
题意
\(~~~~\) 给一棵 \(n\) 个点的树，每条边双向分别有一个权值。现给出 \(q\) 个询问，每个询问可以指定 \(e_i\) 个点为特殊点，对每个特殊点所有非该特殊点到该点的路径相同方向上的边免费，求最小代价。
\(~~~~\) \(1\leq n\leq 2\times 10^5,q\leq n\)。
题解
\(~~~~\) 似乎不难，但我打了3k，/kk
\(~~~~\) 首先由子任务外加手玩不难发现 \(e=1\) 的时候应该做法不大相同，可以发现此时如果把选择的城市作为根，那么最终的答案就是所有向下的边的权值之和，直接换根DP即可，具体实现可见代码。
\(~~~~\) 再看 \(e=2\) ，此时若在某个点 \(u\) 的子树内选两个不属于同一儿子的结点 \(v_1,v_2\)，则节省的代价一定是 \(u\) 作为根时节省的代价加上 \(u\) 到这两个点节省的代价，在上面换根DP二次扫描时取最大值即可。
\(~~~~\) 否则当 \(e>2\) 时，感性认识应该是较之前 \(e-1\) 时选择的点不会改变，只会增加。故每次贪心选取节省的代价最大的那个即可，然后删去它造成负贡献的那些边。不难想到将原树以 \(e=2\) 时其中一个选择的点为根跑一遍dfs序，这样就可以用线段树边贡献。由于每条边最多删一次，所以这一部分复杂度是 \(\mathcal{O(n \log n)}\).
代码
查看代码
#include
#include
#include
#define ll long long
#define PII pair
#define mp(a,b) make_pair(a,b)
using namespace std;
vector < pair > G[200005];
int root,n,q,fa[200005],pos1,pos2;
ll tot,dp[200005],Ans[200005],dis[200005],pos[200005];
void dfs1(int u,int Fa)
{
for(int i=0;iAns[2])
{
Ans[2]=dp[u]+dis[pos[u]]+dis[pos[v]]-dis[u]*2;
pos1=pos[u]; pos2=pos[v];
}
if(dis[pos[u]]>1;
Build(lson); Build(rson);
pushUp(p);
}
void Modify(int p,int l,int r,int lx,int rx,int val)
{
if(lx<=l&&r<=rx)
{
tr[p]+=val;
tag[p]+=val;
return;
}
int mid=(l+r)>>1;pushDown(p);
if(lx<=mid) Modify(lson,lx,rx,val);
if(mid