XCOJ 1103 (LCA+樹鏈最大子段和)

题目链接: http://xcacm.hfut.edu.cn/problem.php?id=1103

题目大意:链更新。链查询,求树链的最大子段和。(子段可以为空)

解题思路:

将所有Query离线存储,并且注明哪个是更新,哪个是查询。

Tarjan离线处理中,记录每个结点的前驱,p[v]=u。

若更新,从u点回溯到LCA,从v点回溯到LCA,逐个修改。

若查询,将u点回溯到LCA,LCA,v点回溯到LCA的倒序拼成一个序列,求最大子段和。

值得注意的是,子段和全为负值的时候,ans=max(0,ans),即不要任何插线板(原题意思不明)。

#include "cstdio"
#include "cstring"
#include "vector"
#include "algorithm"
using namespace std;
#define maxn 105
#define inf 0x3f3f3f3f
int head[maxn],qhead[maxn],lag[maxn],kth[maxn],tot1,tot2,f[maxn],vis[maxn],ancestor[maxn],p[maxn],s1[maxn],s2[maxn];
bool isUpdate[maxn];
struct Edge
{
    int to,next;
}e[maxn*2];
struct Query
{
    int from,to,next,idx,c;
}q[maxn*2];
void addedge(int u,int v)
{
    e[tot1].to=v;
    e[tot1].next=head[u];
    head[u]=tot1++;
}
void addquery(int u,int v,int idx,int c=inf)
{
    q[tot2].from=u;
    q[tot2].to=v;
    q[tot2].next=qhead[u];
    q[tot2].idx=idx;
    if(c!=inf) q[tot2].c=c;
    qhead[u]=tot2++;
}
int find(int x) {return x!=f[x]?f[x]=find(f[x]):x;}
void Union(int u,int v)
{
    u=find(u),v=find(v);
    if(u!=v) f[v]=u;
}
void LCA(int u)
{
    vis[u]=true;
    f[u]=u;
    for(int i=head[u];i!=-1;i=e[i].next)
    {
        int v=e[i].to;
        if(!vis[v])
        {
            p[v]=u;
            LCA(v);
            Union(u,v);
        }
    }
    for(int i=qhead[u];i!=-1;i=q[i].next)
    {
        int v=q[i].to;
        if(vis[v]) ancestor[q[i].idx]=find(v);
        //or storage e[i].lca=e[i^1].lca=find(v)
    }
}
int sum(int num)
{
    s2[0]=s1[0];
    int Max=s2[0];
    for(int i=1; i<num; i++)
    {
        if(s2[i-1]>0) s2[i]=s2[i-1]+s1[i];
        else s2[i]=s1[i];
        if(s2[i]>Max) Max=s2[i];
    }
    return max(0,Max);
}
int main()
{
    //freopen("in.txt","r",stdin);
    int T,n,m,u,v,c,cmd,qcnt=0;
    scanf("%d",&n);
    tot1=tot2=0;
    memset(head,-1,sizeof(head));
    memset(qhead,-1,sizeof(qhead));
    memset(vis,0,sizeof(vis));
    memset(isUpdate,0,sizeof(isUpdate));
    for(int i=1;i<=n;i++) scanf("%d",&lag[i]);
    for(int i=0; i<n-1; i++)
    {
        scanf("%d%d",&u,&v);
        addedge(u,v);
        addedge(v,u);
    }
    scanf("%d",&m);
    for(int i=0; i<m; i++)
    {
        scanf("%d",&cmd);
        if(cmd==2)
        {
            scanf("%d%d%d",&u,&v,&c);
            addquery(u,v,i,c);
            addquery(v,u,i,c);
            isUpdate[i]=true;
        }
        else
        {
            scanf("%d%d",&u,&v);
            addquery(u,v,i);
            addquery(v,u,i);
        }
    }
    LCA(1);
    vector<int> ans;
    for(int i=0; i<tot2; i=i+2)
    {
        int u=q[i].from,v=q[i].to,idx=q[i].idx;
        int ed=ancestor[idx],cnt=0;
        if(isUpdate[qcnt])
        {
            int c=q[i].c;
            while(u!=ed) lag[u]=c,u=p[u];
            lag[ed]=c;
            while(v!=ed) lag[v]=c,v=p[v];
        }
        else
        {
            while(u!=ed) s1[cnt++]=lag[u],u=p[u];
            s1[cnt++]=lag[ed];
            vector<int> rev;
            while(v!=ed) rev.push_back(lag[v]),v=p[v];
            for(int j=rev.size()-1; j>=0; j--) s1[cnt++]=rev[j];
            int x=sum(cnt);
            ans.push_back(x);
        }
        qcnt++;
    }
    for(int i=0;i<ans.size()-1;i++) printf("%d ",ans[i]);
    printf("%d\n",ans[ans.size()-1]);
}

 

更多相关文章
  • 题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=3078 题目大意:定点修改.查询树中任意一条树链上,第K大值. 解题思路: 先用离线Tarjan把每个Query树链的LCA求出来. LCA中对连接树Dfs的时候,令p[v]=u,记录v的前驱. LCA
  • 题目链接: BZOJ - 3626   题目分析 考虑这样的等价问题,如果我们把一个点 x 到 Root 的路径上每个点的权值赋为 1 ,其余点的权值为 0,那么从 LCA(x, y) 的 Depth 就是从 y 到 Root 的路径上的点权和. 这个方法是可以叠加的,这是非常有用的一点.如果我们把
  • hdu3699Aragorns Story樹鏈剖分模板題
    樹鏈剖分學習blog:http://blog.csdn.net/jiangshibiao/article/details/24669751 關於這題的學習blog:http://blog.csdn.net/acdreamers/article/details/10594121 下面來說說樹鏈剖分の我 ...
  • They say that Berland has exactly two problems, fools and roads. Besides, Berland has n cities, populated by
  • 從lca到樹鏈剖分 bestcoder round#45 1003
    bestcoder round#45 1003 题,给定两个点,要我们求这两个点的树上路径所经过的点的权值是否出现过奇数次.如果是一般人,那么就是用lca求树上路径,然后判断是否出现过奇数次(用异或),高手就不这么做了,直接树链剖分.为什么不能用lca,因为如果有树退化成链,那么每次询问的复杂度是O
  • 2243: [SDOI2011]染色 Time Limit: 20 Sec  Memory Limit: 256 MB 题目连接 http://www.lydsy.com/JudgeOnline/problem.ph
  • BZOJ 1103: POI2007大都市meg( 樹鏈剖分 )
    早上数学考挂了...欲哭无泪啊下午去写半个小时政治然后就又可以来刷题了..树链剖分 , 为
  • ACdream 1103 瑤瑤正式成爲CEO(樹鏈剖分+費用流)
    Problem Description 瑶瑶(tsyao)是某知名货运公司(顺丰)的老板,
一周排行