【BZOJ2117】 [2010国家集训队]Crash的旅游计划

Dear 丶 2021-12-20 10:15 257阅读 0赞

## 【BZOJ2117】 \[2010国家集训队\]Crash的旅游计划 ##

### Description ###

眼看着假期就要到了，Crash由于长期切题而感到无聊了，因此他决定利用这个假期和好友陶陶一起出去旅游。 Crash和陶陶所要去的城市里有$N (N > 1) $个景点，Crash用正整数\$1\$到\$N\$给景点标号。这些景点之间通过\$N − 1\$条无向道路相连，每条道路有一个长度，并且保证任意两个景点之间都有且仅有一条路径相连。现在对于一个景点\$s\$，Crash和陶陶从\$s\$出发，然后访问一个景点序列\$\{v0, v1, v2, … , vk\}\$，其中\$v0\$就是\$s\$，且\$vi-1\$和\$vi(0 < i ≤ k)\$之间有道路相连。需要注意的是，陶陶和Crash访问的景点序列中不会只有景点\$s\$。为了使旅程不显得乏味，在一个景点序列里他们不会重复走某条道路。我们定义这个序列的旅游代价为经过道路的长度和。下面问题出现了：陶陶：我们走一条景点数最多的景点序列吧。 Crash：倒，你想把我累死啊。陶陶：谁叫你整天坐在电脑前面，不出来锻炼，这下子傻了吧，哈哈哈哈~~ Crash：不行，如果你非要走景点数最多的我就不陪你走了。陶陶：笑喷油你很跳嘛！ Crash：这样吧，我们来写伸展树，如果我写的比你快，你就要听我的。陶陶：这样不公平哎，我们来玩PES吧，当然你要让我选法国队，如果你输了你就要听我的。 Crash：倒，你这是欺负我，T\_T~ 陶陶：笑喷油好说话哎。 Crash：囧…… …… 这样搞了半天，最终陶陶和Crash用很多次包剪锤决定出选择旅游代价第K小 的景点序列。不过呢Crash和陶陶还没确定开始旅行的景点s，因此他希望你对于每个景点i，计算从景点i开始的景点序列中旅游代价第\$K\$小的值。

### Input ###

共\$N\$行。  
第\$1\$行包含一个字符和两个正整数，字符为ABCD中的一个，用来表示这个测试数据的类型（详见下面的数据规模和约定），另外两个正整数分别表示\$N\$和\$K (K < N)\$。  
第\$2\$行至第\$N\$行，每行有三个正整数\$u、v\$和\$w (u, v ≤ N，w ≤ 10000)\$。表示\$u\$号景点和\$v\$号景点之间有一条道路，长度为\$w\$。  
输入文件保证符合题目的约定，即任意两个景点之间都有且仅有一条路径相连。

### Output ###

共N行，每行有一个正整数。第i行的正整数表示从\$i\$号景点开始的景点序列中旅游代价第\$K\$小的代价。

### Sample Input ###

A 6 3  
1 2 2  
1 3 4  
1 4 3  
3 5 1  
3 6 2

### Sample Output ###

4  
6  
4  
7  
5  
6

有一道题题意一样，数据范围\$N<15000\$。对于那个数据范围小一点的题我们可以用经典的换根操作。换根时我们要支持区间加，全局询问小于某个数\$K\$的数量(因为要二分)。这就是个**经典的分块问题**。

然后看这道数据范围大了很多的题。这种询问全树信息的题大概率是用点分治。我们点分治过后建出了一颗点分树。询问一个点的时候就直接在点分树上暴力跳父亲，然后在每一层的父亲上都查找一次。

不知道为什么，带修改的题容易让我联想到动态点分治，这种不带修的点分树题就容易懵逼...

做这道题让我明白一个残酷的道理：询问全树的路径是**不能**用线段树合并或者主席树之类的。

代码：

#include<bits/stdc++.h>
    #define ll long long
    #define N 100005
    
    using namespace std;
    inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}
    
    int n,k;
    struct road {int to,next,w;}s[N<<1];
    int h[N],cnt;
    void add(int i,int j,int w) {s[++cnt]=(road) {j,h[i],w};h[i]=cnt;}
    
    int fa[N][20];
    int dep[N];
    int dis[N];
    void dfs(int v) {
        for(int i=1;i<=16;i++) fa[v][i]=fa[fa[v][i-1]][i-1];
        for(int i=h[v];i;i=s[i].next) {
            int to=s[i].to;
            if(to==fa[v][0]) continue ;
            fa[to][0]=v;
            dep[to]=dep[v]+1;
            dis[to]=dis[v]+s[i].w;
            dfs(to);
        }
    }
    
    int lca(int a,int b) {
        if(dep[a]<dep[b]) swap(a,b);
        for(int i=16;i>=0;i--)
            if(fa[a][i]&&dep[fa[a][i]]>=dep[b])
                a=fa[a][i];
        if(a==b) return a;
        for(int i=16;i>=0;i--)
            if(fa[a][i]!=fa[b][i])
                a=fa[a][i],b=fa[b][i];
        return fa[a][0];
    }
    int Get_dis(int a,int b) {return dis[a]+dis[b]-2*dis[lca(a,b)];}
    int size[N],mx[N],rt;
    int sum;
    int pr[N],fr[N];
    bool vis[N];
    
    void Get_root(int v,int fr) {
        ::fr[v]=fr;
        size[v]=1;
        mx[v]=0;
        for(int i=h[v];i;i=s[i].next) {
            int to=s[i].to;
            if(vis[to]||to==fr) continue ;
            Get_root(to,v);
            size[v]+=size[to];
            mx[v]=max(mx[v],size[to]);
        }
        mx[v]=max(mx[v],sum-size[v]);
        if(mx[rt]>mx[v]) rt=v;
    }
    
    vector<int>my[N],f[N];
    void statis(int v,int fr,int dep,int x,int y) {
        my[x].push_back(dep);
        f[y].push_back(dep);
        for(int i=h[v];i;i=s[i].next) {
            int to=s[i].to;
            if(to==fr||vis[to]) continue ;
            statis(to,v,dep+s[i].w,x,y);
        }
    }
    
    void solve(int v) {
        vis[v]=1;
        if(fr[v]) size[fr[v]]=sum-size[v];
        my[v].push_back(0);
        for(int i=h[v];i;i=s[i].next) {
            int to=s[i].to;
            if(vis[to]) continue ;
            sum=size[to];
            rt=0;
            Get_root(to,v);
            pr[rt]=v;
            statis(to,v,s[i].w,v,rt);
            solve(rt);
        }
    }
    
    int query(int v,int x) {
        int ans=0;
        ans=lower_bound(my[v].begin(),my[v].end(),x)-my[v].begin();
        for(int i=v;pr[i];i=pr[i]) {
            int d=Get_dis(v,pr[i]);
            ans+=lower_bound(my[pr[i]].begin(),my[pr[i]].end(),x-d)-my[pr[i]].begin();
            ans-=lower_bound(f[i].begin(),f[i].end(),x-d)-f[i].begin();
        }
        return ans;
    }
    
    int main() {
        mx[0]=1e9;
        n=Get(),k=Get();
        k++;
        int a,b,c;
        for(int i=1;i<n;i++) {
            a=Get(),b=Get(),c=Get();
            add(a,b,c),add(b,a,c);
        }
        dfs(1);
        sum=n;
        Get_root(1,0);
        solve(rt);
        for(int i=1;i<=n;i++) {
            sort(my[i].begin(),my[i].end());
            sort(f[i].begin(),f[i].end());
        }
        for(int i=1;i<=n;i++) {
            int l=0,r=1e9,mid;
            while(l<r) {
                mid=l+r+1>>1;
                if(query(i,mid)>=k) r=mid-1;
                else l=mid;
            }
            cout<<l<<"\n";
        }
        return 0;
    }

转载于:https://www.cnblogs.com/hchhch233/p/10471621.html