首页 > 代码库 > TC--SRM-703-Div2-1000-TreeDiameters

TC--SRM-703-Div2-1000-TreeDiameters

2024-08-27 03:18:59   221人阅读

题目大意 ：

定义树的价值为一棵树上距离为树的直径的点对的个数。

给定一颗树，让你求这个树的一个连通子图形成的树的价值最大值是多少。

 

 

首先可以想到一棵树的所有最大直径必然要经过同一点，如果有两条直径不相交，那么必然可以找到一条更长的链。

再者，如果确定了相交的这个点，对于所有这点的子树的最大深度必然只有一个与其他不同或都相同。

那么我们只用把所有的点当做直径的交点，把每个子树每个深度有多少点处理出来，然后计算所有相同的情况。

但是有不同的怎么办？枚举直径长度再计算肯定会超时。但是我们可以观察到，如果长度相差超过1，我们可以把交点向深的那棵子树里移动一下，也就是说在计算深子树的根时会计算到，所以我们只用计算其他相同深树只多1的情况。

 

代码 ：

class TreeDiameters {
    public:
        
    #define MAXN 1005
    int head[MAXN],cnt;
    struct Edge{
        int to,next;
    }e[MAXN*2];
    inline void insert(int a,int b) {
        e[++cnt].next=head[a];head[a]=cnt;e[cnt].to=b;
        e[++cnt].next=head[b];head[b]=cnt;e[cnt].to=a;
    }
    
    int tot[MAXN],dep[MAXN][MAXN],all[MAXN];
    void dfs(int s,int v,int fa,int d) {
        dep[s][d]++;
        for(int i=head[v];i;i=e[i].next) 
            if(e[i].to!=fa) dfs(s,e[i].to,v,d+1);
    }
    
    int ans,n;
    void work(int v) {
        memset(tot,0,sizeof(tot));tot[0]=1;
        memset(all,0,sizeof(all));
        for(int i=head[v];i;i=e[i].next) {
            memset(dep[e[i].to],0,sizeof(dep[e[i].to]));
            dfs(e[i].to,e[i].to,v,1);
            for(int j=1;j<=n;j++) {
                all[j]+=tot[j]*dep[e[i].to][j];
                tot[j]+=dep[e[i].to][j];
                ans=max(ans,all[j]);
            }
        }
        for(int i=head[v];i;i=e[i].next) {
            for(int j=0;j<=n;j++) {
                ans=max(ans,(tot[j]-dep[e[i].to][j])*dep[e[i].to][j+1]);
            }
        }
    }
    
    int getMax(vector<int> p) {
        n=p.size();ans=0;
        for(int i=0;i<n;i++) insert(p[i],i+1);
        for(int i=0;i<=n;i++) work(i);
        return ans;
    }
};

 

TC--SRM-703-Div2-1000-TreeDiameters


联系
我们