Split The Tree(dfs序加统计区间不同数的个数）

题目描述

For their physical fitness program, N (2 ≤ N ≤ 1,000,000) cows have decided to run a relay race using the T (2 ≤ T ≤ 100) cow trails throughout the pasture.
Each trail connects two different intersections (1 ≤ I1i ≤ 1,000; 1 ≤ I2i ≤ 1,000), each of which is the termination for at least two trails. The cows know the lengthi of each trail (1 ≤ lengthi ≤ 1,000), the two intersections the trail connects, and they know that no two intersections are directly connected by two different trails. The trails form a structure known mathematically as a graph.
To run the relay, the N cows position themselves at various intersections (some intersections might have more than one cow). They must position themselves properly so that they can hand off the baton cow-by-cow and end up at the proper finishing place.
Write a program to help position the cows. Find the shortest path that connects the starting intersection (S) and the ending intersection (E) and traverses exactly N cow trails.

输入

* Line 1: Four space-separated integers: N, T, S, and E
* Lines 2..T+1: Line i+1 describes trail i with three space-separated integers: lengthi , I1i , and I2i

输出

* Line 1: A single integer that is the shortest distance from intersection S to intersection E that traverses exactly N cow trails.

样例输入

样例输出

所谓dfs序，就是把一棵树根据遍历的顺序压进一个序列里，这样我们就可以用线段树树状数组等各种骚操作搞它了。

我们dfs后，一棵树变成了一段序列。

然后对于每个节点，它的子树一定是一段连续的区间，那么问题就转化成了给定一段区间，求区间不同数的个数加上剩余数不同数的个数，我们把序列延长一倍，就变成了统计两段连续区间内不同数的个数。树状数组瞎搞即可。

#include <bits/stdc++.h>
#define maxn 200005
using namespace std;
struct edges
{
    int u,v,next;
}edge[maxn];
int head[maxn];
int cnt=0;
int n;
void addedge(int u,int v)
{
    edge[cnt].u=u;
    edge[cnt].v=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
int sizes[maxn];
int in[maxn];//in表示遍历的时间戳
map<int,int> Mp;
int out[maxn];//出来的时间戳，那么子树大小（包括本身）就是out[i]-in[i]
bool vis[maxn];
int x=1;
void dfs(int num)//dfs序
{
    for(int i=head[num];i!=-1;i=edge[i].next)
    {
        int v=edge[i].v;
        if(!vis[v])
        {
            vis[v]=true;
            in[v]=x++;
            Mp[x-1]=v;
            dfs(v);
            out[v]=x;
        }
    }
}
int ans[maxn];
int tree[maxn];
int lowbit(int x)
{
    return x&(-x);
}
void add(int pos,int val)
{
    for(int i=pos;i<=n;i+=lowbit(i))
    {
        tree[i]+=val;
    }
}
int sum(int x)
{
    int res=0;
    for(int i=x;i>0;i-=lowbit(i))
    {
        res+=tree[i];
    }
    return res;
}
struct quer
{
    int l,r,id;
}query[maxn*2];
bool cmp(quer a,quer b)
{
    return a.r<b.r;
}
int main()
{
    int i;
    //freopen("in.txt","r",stdin);
    scanf("%d",&n);
    memset(head,-1,sizeof(head));
    for(int i=2;i<=n;i++)
    {   int v;
        scanf("%d",&v);
        addedge(i,v);
        addedge(v,i);
    }
    vis[1]=true;
    in[1]=x++;
    Mp[1]=1;
    dfs(1);
    out[1]=x;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&sizes[in[i]]);
    }
    for(int i=n+1;i<=2*n;i++)
    {
        sizes[i]=sizes[i-n];
    }
    n*=2;
    int index=0;
    for(int i=2;i<=n/2;i++)//这一步是在枚举每一棵树的子树，把它加到询问里。
    {
        int v=Mp[i];
        int l=i;
        int r=out[v]-1;
        query[index].id=index;
        query[index].l=l;
        query[index++].r=r;
        query[index].id=index;
        query[index].l=r+1;
        int tmp=n/2-(r-l+1);
        query[index].r=query[index].l+tmp-1;
        index++;
    }
    sort(query,query+index,cmp);
    int  cur=1;
    Mp.clear();
    for(int i=0;i<index;i++)//树状数组离线搞
    {
        for(int j=cur;j<=query[i].r;j++)
        {
            if(Mp[sizes[j]]!=0)
            {
                add(Mp[sizes[j]],-1);
            }
            add(j,1);
            Mp[sizes[j]]=j;
        }
        cur=query[i].r+1;
        ans[query[i].id]=sum(query[i].r)-sum(query[i].l-1);
    }
    int res=0;
    for(int i=0;i<index;i+=2)
    {
        res=max(res,ans[i]+ans[i+1]);
    }
    printf("%d
",res);
    return 0;
}