11070: 小P的Civilization V

时间限制: 1 Sec  内存限制: 128 MB

提交: 27  解决: 5

[] [] [] [命题人:]

题目描述

小P最近在玩Civilization V，游戏的地图是一棵树，树的每个节点都可以当作战场，刚开始每个节点的战斗加成为0

现在小P拥有两种人员：

一种是工人，每个工人会有一个起点u和终点v，工人可以使u−>v路径上每个节点的战斗加成+1

一种是骑兵，每个战士也有一个起点u和终点v，战士可以选择u−>v路径上任意节点战斗

现有m个工人和q个骑兵，问每个骑兵作战最多可以拥有多少战斗加成

 

输入

第一行三个整数n,m,q

接下来一行n−1个数，第i个数fi表示第i+1个节点的父亲

接下来m行，每行两个整数u,v，表示一个工人

接下来q行，每行两个整数u,v，表示一个骑兵

 

输出

q行，对于每个骑兵，输出他作战最多可以拥有多少战斗加成

 

样例输入

复制样例数据

5 5 51 1 1 4 4 54 14 35 34 51 33 51 15 24 2

样例输出

35355

 

提示

对于15%的数据，保证n,q≤1000

对于另外15%的数据，保证fi=i

对于另外10%的数据，保证所有u=v

对于另外10%的数据，保证工人的u=v

对于另外10%的数据，保证骑兵的u=v

对于100%的数据，保证n,q≤500,000且fi≤i

Solution:

树上差分，记得算一下平方的最大范围，否则会TLE，另外点权可以映射到边权上，注意小的细节就可以了。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include
          
           #define REP(i, a, b) for(int i = (a); i <= (b); ++ i)#define REP(j, a, b) for(int j = (a); j <= (b); ++ j)#define PER(i, a, b) for(int i = (a); i >= (b); -- i)using namespace std;const int maxn=5e5+10;template 
           
            inline void rd(T &ret){ char c; ret = 0; while ((c = getchar()) < '0' || c > '9'); while (c >= '0' && c <= '9'){ ret = ret * 10 + (c - '0'), c = getchar(); }}int n,m,q,dh;struct node{ int v,w,nx;}p[maxn*2];int tot,head[maxn],tmp,depth[maxn],fa[maxn][25],cnt[maxn],val[maxn][20];void addedge(int u,int v){p[++tot].v=v,p[tot].nx=head[u],head[u]=tot;}void dfs(int x){ REP(i,1,dh){ fa[x][i]=fa[fa[x][i-1]][i-1]; } for(int i=head[x];i;i=p[i].nx){ int to=p[i].v; depth[to]=depth[x]+1; fa[to][0]=x; dfs(to); }}int lca(int x,int y){ if(depth[x]
            
             =0;i--){ if(depth[x]>depth[y]&&depth[fa[x][i]]>=depth[y])x=fa[x][i]; } PER(i,dh,0){ if(fa[x][i]!=fa[y][i]){ x=fa[x][i],y=fa[y][i]; } } if(x!=y){ return fa[x][0]; } return x;}void gt(int cur){ for(int i=head[cur];i;i=p[i].nx){ int to=p[i].v; gt(to); cnt[cur]+=cnt[to]; }}void dfs2(int x){ REP(i,1,dh)val[x][i]=max(val[x][i-1],val[fa[x][i-1]][i-1]); for(int i=head[x];i;i=p[i].nx){ int to=p[i].v; val[to][0]=cnt[to]; dfs2(to); }}int lca2(int x,int y){ if(depth[x]
             
              =0;i--){ if(depth[x]>depth[y]&&depth[fa[x][i]]>=depth[y])ans=max(ans,val[x][i]),x=fa[x][i]; } PER(i,dh,0){ if(fa[x][i]!=fa[y][i]){ ans=max(ans,max(val[x][i],val[y][i])); x=fa[x][i],y=fa[y][i]; } } if(x!=y){ ans=max(ans,max(val[x][0],val[y][0])); ans=max(ans,cnt[fa[x][0]]); return ans; } ans=max(ans,cnt[x]); return ans;}int main(){ rd(n),rd(m),rd(q); depth[1]=1; dh=floor(log(n+0.0)/log(2.0)); REP(i,2,n){ rd(tmp); addedge(tmp,i); } dfs(1); REP(i,1,m){ int u,v; rd(u),rd(v); int LCA=lca(u,v); cnt[u]++,cnt[v]++,cnt[LCA]--,cnt[fa[LCA][0]]--; } gt(1); dfs2(1); REP(i,1,q){ int u,v; rd(u),rd(v); printf("%d\n",lca2(u,v)); } return 0;}