HDU 5401 Persistent Link/cut Tree

忘是亡心i 2022-08-04 05:19 83阅读 0赞

考虑爆搜，树i生成后，两两点对路径分成两部分，一部分不经过中间的边，那么就是ai和bi的答案，如果经过中间的边，首先计算中间这条边出现的次数，也就是ai,bi子树大小的乘积。对于ai，对答案的贡献为所有点到ci的距离和乘上bi的子树大小。bi同理。

那么转化为计算在树i中，所有点到某个点j的距离和。假设j在ai内，那么就转化成了ai内j这个点的距离总和加上bi内所有点到di的总和加上di到j的距离乘上子树bi的大小，称作第一类询问。

这样就化成了在树i中两个点j和k的距离，如果在同一棵子树中，可以递归下去，否则假设j在ai中k在bi中，那么距离为j到ci的距离加上k到di的距离加上li ，称作第二类询问。

然后对两类询问全都记忆化搜索即可。

接着考虑计算一下复杂度。

对于第二类询问，可以考虑询问的过程类似于线段树，只会有两个分支，中间的部分已经记忆化下来，不用再搜，时间复杂度O(m)。

我们分析一下复杂度，首先对于第一类询问，在bi中到di的点距离和已经由前面的询问得到，那么就转化为一个第一类询问和一个第二类询问，最多会被转化成O(m)个第二类询问。

所以每个询问复杂度是O(m2),总复杂度O(m3)。

这里的离散化姿势特别不舒服，但是据队友说，不这样写会TLE….虽然觉得应该不会吧

// whn6325689
    // Mr.Phoebe
    // http://blog.csdn.net/u013007900
    #include <algorithm>
    #include <iostream>
    #include <iomanip>
    #include <cstring>
    #include <climits>
    #include <complex>
    #include <fstream>
    #include <cassert>
    #include <cstdio>
    #include <bitset>
    #include <vector>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <ctime>
    #include <set>
    #include <map>
    #include <cmath>
    #include <functional>
    #include <numeric>
    #pragma comment(linker, "/STACK:1024000000,1024000000")
    
    using namespace std;
    
    #define eps 1e-9
    #define PI acos(-1.0)
    #define INF 0x3f3f3f3f
    #define LLINF 1LL<<62
    #define speed std::ios::sync_with_stdio(false);
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;
    typedef pair<ll, ll> pll;
    typedef complex<ld> point;
    typedef pair<int, int> pii;
    typedef pair<pii, int> piii;
    typedef vector<int> vi;
    
    #define CLR(x,y) memset(x,y,sizeof(x))
    #define CPY(x,y) memcpy(x,y,sizeof(x))
    #define clr(a,x,size) memset(a,x,sizeof(a[0])*(size))
    #define cpy(a,x,size) memcpy(a,x,sizeof(a[0])*(size))
    
    #define mp(x,y) make_pair(x,y)
    #define pb(x) push_back(x)
    #define lowbit(x) (x&(-x))
    
    #define MID(x,y) (x+((y-x)>>1))
    #define ls (idx<<1)
    #define rs (idx<<1|1)
    #define lson ls,l,mid
    #define rson rs,mid+1,r
    #define root 1,1,n
    
    template<class T>
    inline bool read(T &n)
    {
        T x = 0, tmp = 1;
        char c = getchar();
        while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
        if(c == EOF) return false;
        if(c == '-') c = getchar(), tmp = -1;
        while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
        n = x*tmp;
        return true;
    }
    template <class T>
    inline void write(T n)
    {
        if(n < 0)
        {
            putchar('-');
            n = -n;
        }
        int len = 0,data[20];
        while(n)
        {
            data[len++] = n%10;
            n /= 10;
        }
        if(!len) data[len++] = 0;
        while(len--) putchar(data[len]+48);
    }
    //-----------------------------------
    
    const int MOD=1e9+7;
    
    int n,m;
    int idx[150];
    ll num[66];
    set<ll> pos[66];
    vector<ll> g[66];
    ll dis[66][150][150];
    ll todis[66][150];
    ll dp[66];
    struct QUERRY
    {
        int a,b;
        ll c,d,l;
        void input()
        {
            read(a),read(b),read(c),read(d),read(l);
        }
    } t[66];
    
    
    //离散化
    int discre(int i,ll b)
    {
        return lower_bound(g[i].begin(),g[i].end(),b)-g[i].begin();
    }
    
    //离散化的初始准备
    void init()
    {
        for(int i=m; i>=1; i--)
        {
            for(set<ll>::iterator it=pos[i].begin(); it!=pos[i].end(); it++)
            {
                if(*it>=num[t[i].a])
                    pos[t[i].b].insert(*it-num[t[i].a]);
                else
                    pos[t[i].a].insert(*it);
                g[i].pb(*it);
            }
        }
        for(set<ll>::iterator it=pos[0].begin(); it!=pos[0].end(); it++)
            g[0].pb(*it);
    }
    
    //只维护了上三角
    ll getdist(int v,int l,int r)
    {
        if(l<=r)return dis[v][l][r];
        return dis[v][r][l];
    }
    
    ll solve(int v)
    {
        int le=t[v].a,ri=t[v].b;
        ll num1=num[le]%MOD,num2=num[ri]%MOD;
        int len=g[v].size();
        //子树的贡献
        dp[v]=(dp[le]+dp[ri])%MOD;
        //新加边的贡献
        dp[v]=(dp[v]+(num1*num2%MOD)*t[v].l%MOD)%MOD;
        //其他节点到连接节点的贡献
        int lec=discre(le,t[v].c);
        int rid=discre(ri,t[v].d);
        dp[v]=(dp[v]+todis[le][lec]*num2%MOD+todis[ri][rid]*num1%MOD)%MOD;
        //分别在两棵子树上面离散化
        for(int i=0; i<len; i++)
        {
            if(g[v][i]<num[le])
                idx[i]=discre(le,g[v][i]);
            else
                idx[i]=discre(ri,g[v][i]-num[le]);
        }
        //更新整棵树到出节点的距离
        for(int i=0; i<len; i++)
        {
            if(g[v][i]<num[le])
                todis[v][i]=(todis[le][idx[i]]+todis[ri][rid]+num2*(t[v].l+getdist(le,lec,idx[i]))%MOD)%MOD;
            else
                todis[v][i]=(todis[ri][idx[i]]+todis[le][lec]+num1*(t[v].l+getdist(ri,rid,idx[i]))%MOD)%MOD;
        }
    
        //更新连出点之间的距离
        for(int i=0; i<len; i++)
        {
            dis[v][i][i]=0;
            for(int j=i+1; j<len; j++)
            {
                if(g[v][i]<num[le] && g[v][j]<num[le])
                    dis[v][i][j]=dis[le][idx[i]][idx[j]];
                else if(g[v][i]>=num[le]&&g[v][j]>=num[le])
                    dis[v][i][j]=dis[ri][idx[i]][idx[j]];
                else
                    dis[v][i][j]=getdist(le,idx[i],lec)+getdist(ri,idx[j],rid)+t[v].l;
                dis[v][i][j]%=MOD;
            }
        }
    }
    
    int main()
    {
        freopen("data.txt","r",stdin);
        while(read(m))
        {
            for(int i=0; i<=m; i++)
            {
                g[i].clear();
                pos[i].clear();
            }
            CLR(num,0);
            CLR(dp,-1);
            CLR(todis,0);
            num[0]=1;
            dp[0]=0;
            for(int i=1; i<=m; i++)
            {
                t[i].input();
                pos[t[i].a].insert(t[i].c);
                pos[t[i].b].insert(t[i].d);
                num[i]=num[t[i].a]+num[t[i].b];
            }
            init();
            for(int i=0; i<=m; i++)
            {
                int len=g[i].size();
                for(int j=0; j<len; j++)
                    for(int k=0; k<len; k++)
                        dis[i][j][k]=0;
            }
            for(int i=1; i<=m; i++)
            {
                solve(i);
                write(dp[i]),putchar('\n');
            }
        }
        return 0;
    }