如果没有k个城市可以独立供电，我们就直接找到x和y的中位数，然后计算距离和就可以了，现在要去掉k个城市，很明显，中位数位置的偏移不超过k/2+1,这样，我们分别枚举x和y在[n/2-k/2-1,n/2+k/2+1]的位置就可以找到最优情况了.                                  

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;int tx[1010],ty[1010],change[1010],n,k;struct node{    int c,x,y;}va[1010];int cal(int posx,int posy){    priority_queue
          
           
            ,greater
            
              >q; int ans=0; for(int i=0;i
            
           
          
         
        
       
      

 

　　把树转化成1维，然后线段树，转化的方法可以先写，和ZOJ3686不同的是，更新的值根据层数是递增的，所以直接区间更新明显是不行的，观察发现，树的层数可以保证下面一层是上面一层+1，那么给定一个根节点a,假设操作为A a k，a为根结点的子树的所有节点深度和为S，更新实际增加值为X，那么满足S-(dep[a]-k)*num=X,其中dep[a]表示a的深度，num表示以a为根的子树的节点个数，可以理解为每个节点多加了(dep[a]-k)，这样，我们只需记录每个区间被增加过多少次和多增加的值，就可以区间更新+延迟标记搞了。

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define maxn 50010#define lson l,m,root<<1#define rson m+1,r,root<<1|1#define INF 0x3f3f3f3f3f3f3f3fllvector
          
           road[maxn];bool mark[maxn];int l[maxn],r[maxn],dep[maxn],num,addcnt[maxn<<2];//sum 多加的权值 cnt加过的次数long long depsum[maxn],sum[maxn<<2],addsum[maxn<<2];void pushup(int root){    sum[root]=sum[root<<1]+sum[root<<1|1];}void dfs(int pos,int deep){    l[pos]=num++;    dep[l[pos]]=deep;    int size=road[pos].size();    for(int i=0;i
           
            >1; int ls=(root<<1); int rs=(root<<1|1); if(addsum[root]!=INF){ if(addsum[ls]==INF) addsum[ls]=0; if(addsum[rs]==INF) addsum[rs]=0; addsum[ls]+=addsum[root]; addsum[rs]+=addsum[root]; addcnt[ls]+=addcnt[root]; addcnt[rs]+=addcnt[root]; sum[ls]+=addcnt[root]*(depsum[mid]-depsum[l-1])-addsum[root]*(mid-l+1); sum[rs]+=addcnt[root]*(depsum[r]-depsum[mid])-addsum[root]*(r-mid); addcnt[root]=0; addsum[root]=INF; }}void update(int l,int r,int root,int s,int e,int add){ if(s<=l&&e>=r){ sum[root]+=depsum[r]-depsum[l-1]-add*(r-l+1); if(addsum[root]==INF) addsum[root]=0; addsum[root]+=add; addcnt[root]++; return; } int m=(l+r)>>1; pushdown(root,l,r); if(m>=s) update(lson,s,e,add); if(m
            
             =r) return sum[root]; double ret=0; int m=(l+r)>>1; pushdown(root,l,r); if(m>=s) ret+=query(lson,s,e); if(m