9/3 树形dp+树的直径+最长路径 +st表

P1352 没有上司的舞会

设计状态： f[u][0]表示u不去舞会，其子树的累加和的最大值 f[u][1]表示u去舞会，其直系下属不去舞会，但已下属为根节点的子树的快乐指数需要累加

#include
#define int long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i>n;
    for(int i=1;i>a[i];
    for(int i=1;i>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
        din[u]++;
    }
    int g;
    for(int i=1;in)
    {
        cnt=0;
        for(int i=0;iv>>w;
            add(i,v,w),add(v,i,w);
        }
        dfs1(1,0);
        dfs2(1,0);
        for(int i=1;iT;
    //while(T--)
        solve();
    return 0;
}

Strategic game

思路是正解，但总是报运行错误，找了半个多小时，索性不找了，可能是码分问题，也不常在这个oj上做题。 问题找到了，在poj上用define int long long要小心！！！ 该问题的本质是求解最少边覆盖。若该点放置士兵，则子结点应选择代价较少的士兵数；若改点不放置士兵，则其子节点必须放置士兵。

#include 
#include 
#include 
#include
//#define int long long
#define endl '\n'
#define For(i,a,b) for(i=(a);iT;
    //while(T--)
        solve();
    return 0;
}

P3088 [USACO13NOV]Crowded Cows S

小工具：可用lowerbound处理每个点所在左右边界的关系

#include
#define int long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i