130324答题报告

130324解题报告

这次周赛选的是两次CF的题。

分别是168div2 170div2

A.Circle Line 水题

B.New Problem

这道题还是蛮有意思的，因为要注意到因为数据范围小而引起的变化。

但是这题n<= 30, 字符串长度<=20。

所以，最多有30*19个长度为2的子串。

但是长度为2的子串一共有26*26。

26*26 > 30*19。

所以这道题我们就只需要枚举长度1的子串和长度2的子串即可。

vector<int>q[Max];__int64 value[Max];__int64 add[Max];__int64 des[Max];int max(int a,int b){return a>b?a:b;}void dfs(int now, int pre){for (int i = 0 ;i < q[now].size(); i ++){int next = q[now][i];if(next != pre){dfs(next,now);add[now] = max(add[now], add[next]);des[now] = max(des[now], des[next]);}}value[now] = value[now] + add[now] - des[now];if(value[now] < 0)add[now] += -(value[now]);elsedes[now] += value[now];}int main(){int n ;cin >> n ;int a,b;for (int i = 0 ;i < n - 1 ; i++){scanf("%d%d",&a,&b);q[b].push_back(a);q[a].push_back(b);}for (int i = 1; i <= n ; i++)scanf("%I64d",&value[i]);dfs(1,-1);cout << add[1] + des[1] <<endl;}

明天还得继续把今天周赛的题给A掉=。=