hdu5242 上海邀請賽 優先隊列+貪心

hdu5242 上海邀請賽 優先隊列+貪心

題意是給你一棵樹 n個點 n-1條邊 起點是1 每個點都有權值 每次能從根節點走到葉子節點 經行k次游戲 每次都是從1開始 拿過的點的權值不能拿第二次 問最大權值和；

開始看到題時也沒想到什麼方法 就按照常規的來 結果超時了 試著優化了好多次 最後過了 百度題解說是樹鏈剖分 醉了 還沒學！！！

說說我的做法吧 map【i】=a表示i節點的跟節點為a節點 從所有葉子節點開始入隊（有點隊列裡有三個變量 分別是節點編號 權值 深度 優先級看代碼 裡面有點貪心的意思） 每次走根節點 如果根節點沒走過 則走它 並把該店權值變為0 否則直接跳到1這個節點（如果一個個跳可能會超時）再入隊 當出隊的編號為1時並且拿的個數小於游戲次數 則拿 否則結束 在跑深度的時候有個優化 開始沒有超時了 如果該節點深度已知了 則以後的根節點就不用跑了！！！ 具體看代碼吧

#include
#include
#include
#include
using namespace std;

int map[100010],mark[100010];
int Deep[100010];
__int64 num[100010];
struct node
{
    __int64 value;
    int ii;
    int deep;
    bool operator < (const node& x) const
    {
        return deep<x.deep||(deep==x.deep&&value<x.value);
    }
}a;
int main()
{
    int T,i,j,n,k,r=1;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&k);
        for(i=1;i<=n;i++)
        {
            scanf("%I64d",&num[i]);
        }
        memset(mark,0,sizeof(mark));
        for(i=1;i<n;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            mark[x]=1;
            map[y]=x;
        }
        priority_queue<node>Q;
        memset(Deep,0,sizeof(Deep));
        for(i=1;i<=n;i++)
        {
            if(mark[i]==0)
            {
                int x=map[i];
                int d=1;
                while(x!=1)
                {    
                    if(Deep[x]>0) {d+=Deep[x];break;}
                    x=map[x];
                    d++;
                }
                x=i;
                while(x!=1)
                {
                    if(Deep[x]>0) break;
                    Deep[x]=d;
                    x=map[x];
                    d--;
                }
                a.deep=Deep[i];
                a.value=num[i];
                a.ii=i;
                Q.push(a);
                
            }
        }
        //for(i=1;i<=n;i++)
        //printf("%d ^^^ %d\n",i,Deep[i]);
        __int64 sum=0;
        int cont=0;
        while(!Q.empty())
        {
            a=Q.top();
            Q.pop();
            int x=map[a.ii];
            /*while(num[x]==0&&x!=1)
            {
                x=map[x];
            }*/
            if(a.ii==1)
            {
                a.value+=num[1];
                num[1]=0;
                sum+=a.value;
                cont++;
                if(cont>=k) break;
            }
            else
            {
                if(num[x]==0)
                {
                    a.ii=1;
                    a.deep=0;    
                }
                else
                {
                    a.ii=x;
                    a.deep=Deep[x];
                    a.value+=num[x];
                    num[x]=0;
                }
                Q.push(a);
            }
        }
        printf("Case #%d: %I64d\n",r++,sum);
    }
    return 0;
}